Наступает новый год. Это значит, что на codeforces пришла пора менять хендлы. Мишке захотелось поменять свой хендл, но таким образом, чтобы люди не забыли, кто он такой.
Чтобы все получилось так, как он хочет, он решил менять только регистры букв. Более формально, за одну смену хендла он может выбрать любой отрезок своего хендла \([i; i + l - 1]\) и сделать tolower или toupper ко всем буквам своего хендла на этом отрезке (более формально, поменять все строчные буквы на отрезке на соответствующие прописные или наоборот). Длина \(l\) фиксирована для всех смен.
Так как на codeforces нельзя слишком часто менять хендлы, всего Мишка может сделать не более \(k\) таких операций. Какого минимального значения может быть \(min(lower, upper)\) (где \(lower\) — количество строчных букв, а \(upper\) — количество прописных букв) после оптимальной последовательности смен?
Выходные данные
Выведите одно целое число — минимальное значение, которого может достигнуть \(min(lower, upper)\) после того, как Мишка сменит свой хендл не более \(k\) раз так, как описано в условии задачи.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7 1 4
PikMike
|
0
|
|
2
|
15 2 2
AaAaAAaaAAAAaaA
|
2
|
|
3
|
14 2 6
aBcdEFGHIJklMn
|
0
|
|
4
|
9 2 2
aAaAAAaaA
|
1
|