Крутий підрядок

Козак Вус вважає рядок крутим, якщо виконуються наступні умови:

1. Усі символи на парних позиціях однакові.

2. Усі символи на непарних позиціях однакові.

Наприклад, рядки 'wow' та 'ftftf' — круті, а рядки 'cabab' та 'abcd' — ні.

У Козака Вуса є рядок $s$ довжини $n$, що складається з малих латинських літер. Він може змінити не більше $k$ символів в ньому так, щоб в рядку був крутий підрядок максимальної можливої довжини. Допоможіть йому знайти цю довжину.

Input

Перший рядок містить два цілі числа $n$ та $k$ ($1\le n\le 5\cdot 10^6$, $0\le k\le 5\cdot 10^6$) — кількість символів в рядку, та кількість символів, які Козак Вус може змінити.

Другий рядок містить рядок $s$, який складається з $n$ малих латинських літер.

Output

Виведіть єдине число — максимально можливу довжину крутого підрядка, яку може отримати Козак Вус.

Examples

Scoring

1. ($7$ балів): $n\le 100$;

2. ($14$ балів): $n\le 3000$;

3. ($33$ бали): $n\le 100000$;

4. ($23$ бали): $k=0$;

5. ($23$ бали): без додаткових обмежень.