A. Путь домой
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Лягушка живет на координатной прямой Ox и должна добраться домой в точку n из точки 1. Она может прыгать вправо на расстояние не более чем d. Таким образом, после прыжка из x она перемещается в точку x + a, где a — целое число от 1 до d.

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

Определите минимальное количество прыжков, которые нужны сделать лягушке, чтобы попасть из точки 1 домой в точку n. Считайте, что изначально лягушка находится в точке 1. Если лягушка не может добраться домой, то выведите -1.

Входные данные

В первой строке записаны два целых числа n и d (2 ≤ n ≤ 100, 1 ≤ d ≤ n - 1) — точка, в которую лягушка хочет попасть, и максимальная длина прыжка лягушки.

Во второй строке записана строка s длины n, состоящая из нулей и единиц. Если очередной символ строки s равен нулю, то в соответствующей точке нет лилии, в противном случае, в соответствующей точке лилия есть. Гарантируется, что первый и последний символы строки s равны единице.

Выходные данные

Если лягушка не сможет попасть домой, выведите -1.

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

Примеры
Входные данные
8 4
10010101
Выходные данные
2
Входные данные
4 2
1001
Выходные данные
-1
Входные данные
8 4
11100101
Выходные данные
3
Входные данные
12 3
101111100101
Выходные данные
4
Примечание

В первом примере лягушка может добраться до дома за два прыжка: первый прыжок из точки 1 в точку 4 (длина прыжка равна трём), а второй прыжок из точки 4 в точку 8 (длина прыжка равна четырём).

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