Після багаторазових пригод Т'Чалле очікує фінальна битва проти Кілмонгера! Так як герої уже дуже втомилися під час фільму, вони вирішили вияснити відношення в більш спокійному інтелектуальному змаганні.
Правила змагань встановили наступні: спочатку Кілмонгер придумує рядок s1s2…sn, що складається з n рядкових латинських літер.
Назвемо грубістю рядки t1t2…tk кількість пар цілих чисел (i,j), де 1≤i<j≤k, при цьому ti= «a
», а також tj= «b
». Іншими словами, грубість рядка — це кількість способів викреслити всі його символи, окрім двох, так, щоб залишився рядок, що складається з двох літер: латинських літер «a
» і «b
» (саме в цьому порядку).
Після того, як Кілмонгер придумав рядок, Т'Чалла повинен вибрати деякий непустий її підрядок slsl+1…sr. При цьому грубість вибраного підрядка не повинен перевищувати число c, інакше за таку грубість Т'Чалла отримає технічну поразку у грі.
Т'Чалла виграє в грі, якщо серед всіх можливих підрядків рядка s, грубість якого не перевищує c, він вибирає максимальний по довжині (будь-який з них, якщо шуканих рядків максимальної довжини декілька). Т'Чалла не просить Вас допомагати йому знаходити шуканий підрядок, бо він сам може справитись з цією задачею, однак для того, щоб провірити себе, він просить вас дізнатися, яка максимальна можлива довжина шуканого підрядка.
Перший рядок вхідних даних містить два цілих числа n і c — довжина рядка, придуманого Кілмонгером, і максимальна дозволена грубість вибраного підрядка (1≤n≤106, 0≤c≤1018).
В другому рядку записано рядок s, задуманий Кілмонгером. Рядок складається з n рядкових латинських букв.
Виведіть єдине число — максимальну довжину підрядка придуманого рядка, який має грубість не більшого c.
Ця задача містить шість підзадач. Для підзадачі виконується додаткові обмеження, вказані нижче. Для отримання балів за підзадачу необхідно пройти всі тести даної підзадачі, а також всі тести всіх попередніх підзадач.
(6 балів): n≤3;
(12 балів): n≤50;
(18 балів): n≤700;
(18 балів): n≤5000;
(24 бали): n≤105;
(22 бали): повні обмеження.