У Кристины есть строка \(s\) длины \(n\), состоящая только из строчных и заглавных латинских букв. За каждую пару из строчной буквы и соответствующей ей заглавной Кристина может получить \(1\) бурль. При этом, пары из символов не могут пересекаться, то есть каждый символ может быть только в одной паре.
Например, если у нее есть строка \(s\) = «aAaaBACacbE», то она может получить бурль за следующие пары символов:
- \(s_1\) = «a» и \(s_2\) = «A»
- \(s_4\) = «a» и \(s_6\) = «A»
- \(s_5\) = «B» и \(s_{10}\) = «b»
- \(s_7\)= «C» и \(s_9\) = «c»
Кристина хочет получить больше бурлей за свою строку, поэтому она собирается совершить над ней не более \(k\) операций. За одну операцию она может:
- либо выбрать строчный символ \(s_i\) (\(1 \le i \le n\)) и сделать его заглавным.
- либо выбрать заглавный символ \(s_i\) (\(1 \le i \le n\)) и сделать его строчным.
Например, при \(k\) = 2 и \(s\) = «aAaaBACacbE» она может совершить одну операцию: выбрать \(s_3\) = «a» и сделать его заглавным. Тогда она получит еще одну пару из \(s_3\) = «A» и \(s_8\) = «a».
Найдите максимальное количество бурлей, которое Кристина может получить за свою строку.
Выходные данные
Для каждого набора входных данных на отдельной строке выведите ровно одно целое число: максимальное количество бурлей, которое Кристина может получить за строку \(s\).
Примечание
Первый набор входных данных разобран в условии.
Во втором наборе входных данных невозможно получить ни одну пару выполнив любое количество операций.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
11 2
aAaaBACacbE
2 2
ab
4 1
aaBB
6 0
abBAcC
5 3
cbccb
|
5
0
1
3
2
|