Школьник Вася получил в подарок на день рождения строку длины n, состоящую из букв «a» и «b». Вася называет привлекательностью строки максимальную длину подстроки (последовательности соседних символов), состоящей из одинаковых символов.
Вася может поменять в исходной строке не более k символов. Какой максимальной привлекательности данной строки он сможет добиться?
Выходные данные
Выведите единственное целое число — максимальная привлекательность строки, которую Вася может получить, изменив в исходной строке не более k символов.
Примечание
В первом примере Вася может получить как строку «aaaa», так и строку «bbbb».
Во втором примере оптимальный ответ достигается на строке «aaaaabaa» или на строке «aabaaaaa».
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 2
abba
|
4
|
|
2
|
8 1
aabaabaa
|
5
|