После многочисленных приключений Т'Чалле предстоит финальная битва против Киллмонгера! Так как герои уже порядком устали за время фильма, они решили выяснить отношения в более спокойном интеллектуальном соревновании.
Правила соревнования установили следующие: сначала Киллмонгер придумывает строку 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 балла): полные ограничения.