Не так грубо!

Після багаторазових пригод Т'Чалле очікує фінальна битва проти Кілмонгера! Так як герої уже дуже втомилися під час фільму, вони вирішили вияснити відношення в більш спокійному інтелектуальному змаганні.

Правила змагань встановили наступні: спочатку Кілмонгер придумує рядок $s_1{s}_2\dots s_n$, що складається з $n$ рядкових латинських літер.

Назвемо грубістю рядки $t_1{t}_2\dots t_k$ кількість пар цілих чисел $(i,j)$, де $1\le i<j\le k$, при цьому $t_i=$ «a», а також $t_j=$ «b». Іншими словами, грубість рядка — це кількість способів викреслити всі його символи, окрім двох, так, щоб залишився рядок, що складається з двох літер: латинських літер «a» і «b» (саме в цьому порядку).

Після того, як Кілмонгер придумав рядок, Т'Чалла повинен вибрати деякий непустий її підрядок $s_l{s}_{l+1}\dots s_r$. При цьому грубість вибраного підрядка не повинен перевищувати число $c$, інакше за таку грубість Т'Чалла отримає технічну поразку у грі.

Т'Чалла виграє в грі, якщо серед всіх можливих підрядків рядка $s$, грубість якого не перевищує $c$, він вибирає максимальний по довжині (будь-який з них, якщо шуканих рядків максимальної довжини декілька). Т'Чалла не просить Вас допомагати йому знаходити шуканий підрядок, бо він сам може справитись з цією задачею, однак для того, щоб провірити себе, він просить вас дізнатися, яка максимальна можлива довжина шуканого підрядка.

Вхідні дані

Перший рядок вхідних даних містить два цілих числа $n$ і $c$ — довжина рядка, придуманого Кілмонгером, і максимальна дозволена грубість вибраного підрядка ($1\le n\le 10^6$, $0\le c\le 10^{18}$).

В другому рядку записано рядок $s$, задуманий Кілмонгером. Рядок складається з $n$ рядкових латинських букв.

Вихідні дані

Виведіть єдине число — максимальну довжину підрядка придуманого рядка, який має грубість не більшого $c$.

Приклади

Оцінювання

Ця задача містить шість підзадач. Для підзадачі виконується додаткові обмеження, вказані нижче. Для отримання балів за підзадачу необхідно пройти всі тести даної підзадачі, а також всі тести всіх попередніх підзадач.

1. ($6$ балів): $n\le 3$;

2. ($12$ балів): $n\le 50$;

3. ($18$ балів): $n\le 700$;

4. ($18$ балів): $n\le 5000$;

5. ($24$ бали): $n\le 10^5$;

6. ($22$ бали): повні обмеження.