Козак Вус вважає рядок крутим, якщо виконуються наступні умови:
Усі символи на парних позиціях однакові.
Усі символи на непарних позиціях однакові.
Наприклад, рядки 'wow'
та 'ftftf'
— круті, а рядки 'cabab'
та 'abcd'
— ні.
У Козака Вуса є рядок s довжини n, що складається з малих латинських літер. Він може змінити не більше k символів в ньому так, щоб в рядку був крутий підрядок максимальної можливої довжини. Допоможіть йому знайти цю довжину.
Перший рядок містить два цілі числа n та k (1≤n≤5⋅106, 0≤k≤5⋅106) — кількість символів в рядку, та кількість символів, які Козак Вус може змінити.
Другий рядок містить рядок s, який складається з n малих латинських літер.
Виведіть єдине число — максимально можливу довжину крутого підрядка, яку може отримати Козак Вус.
(7 балів): n≤100;
(14 балів): n≤3000;
(33 бали): n≤100000;
(23 бали): k=0;
(23 бали): без додаткових обмежень.