eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Гипнотический эксперимент

Гипнотический эксперимент

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB

В проведенном Вами новом эксперименте по гипнозу участвовало n человек. Сейчас эти n человек выстроены в ряд слева направо, причем некоторые из них бодрствуют, а некоторые находятся в гипнозе.

Вам дана строка s длины n, состоящая из нулей и единиц, представляющая текущий статус этих людей, и число k. Если i-й символ s равен 0, то i-й человек слева бодрствует, если равен 1, он находится в гипнозе.

Вы можете выполнить гипнотическое действие не более k раз. За один ход Вы выбираете числа l и r (1lrn) и выполняете гипнотическое действие, которое повлияет только на l-го, (l + 1)-го, ..., r-го человека. После гипнотического действия засыпают только те кто до этого бодрствовал, а те кто находился в гипнотическом состоянии, начинают бодрствовать.

Найдите размер наибольшего интервала, которого можно достичь когда все находятся в гипнотическом состоянии.

Вхідні дані

В первой строке даются два целых числа n и k (1n, k10^5). На следующей строке даётся s. Каждый символ строки s равен или 0 или 1, длина строки равна n.

Вихідні дані

Выведите размер самого большого интервала, который Вы можете получить, когда все находятся в гипнотическом состоянии после применения действия гипноза не более k раз.

Приклад

Вхідні дані #1
5 1
10010
Вихідні дані #1
4
Вхідні дані #2
2 2
11
Вихідні дані #2
2

Примітка

Рассмотрим первый тест. Выбрав l = 2, r = 3, можно загипнотизировать людей на промежутке [2, 3]. В результате 4 последовательных человека окажутся в состоянии гипноза.

Во втором тесте нет необходимости проводить какой-либо гипноз.

Джерело 2023 Азербайджан, Полуфинал, 18 Февраля, 10 - 11 классы