Верный конь Рустама, Рахш, уже не тот, что раньше. Некогда могущественный и быстрый, Рахш со временем стал слабее. Рустам беспокоится, что если слишком много частей тела Рахша потеряют силу одновременно, Рахш может полностью остановиться. Чтобы поддержать своего спутника, Рустам решает укрепить Рахша, чтобы ни одна часть его тела не стала слишком слабой.
Тело Рахша можно представить в виде последовательности пятен, представленных бинарной строкой \(s\) длины \(n\), где символ \(0\) означает слабое место, а \(1\) — сильное. Цель Рустама — убедиться, что ни один интервал из \(m\) последовательных пятен не является полностью слабым (все пятна обозначены \(0\)).
К счастью, Рустам обладает особой способностью под названием Тимар, унаследованной от его матери Рудабе при рождении. С помощью Тимар он может выбрать любой отрезок длины \(k\) и мгновенно усилить его (изменить каждый символ на этом отрезке на \(1\)). Ваша задача состоит в том, чтобы определить минимальное число раз, которое Рустаму нужно использовать Тимар, чтобы на теле Рахша не осталось последовательных полностью слабых участков длины \(m\).
Выходные данные
Для каждого набора входных данных выведите минимальное число раз, которое Рустаму необходимо использовать Тимар, чтобы поддерживать движение Рахша, гарантируя отсутствие последовательных полностью слабых участков длины \(m\).
Примечание
В первом наборе входных данных мы должны применить операцию к каждому символу 0.
Во втором наборе входных данных \(s\) уже удовлетворяет условию.
В третьем наборе входных данных мы можем выполнить операцию над интервалом \([3,4]\) для получения 001100.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
5 1 1
10101
5 2 1
10101
6 3 2
000000
|
2
0
1
|