Лягушка живет на координатной прямой Ox и должна добраться домой в точку n из точки 1. Она может прыгать вправо на расстояние не более чем d. Таким образом, после прыжка из x она перемещается в точку x + a, где a — целое число от 1 до d.
Для каждой точки от 1 до n известно, есть ли в ней лилия. Лягушка может прыгать только по лилиям. Гарантируется, что в точках 1 и n лилии обязательно есть.
Определите минимальное количество прыжков, которые нужны сделать лягушке, чтобы попасть из точки 1 домой в точку n. Считайте, что изначально лягушка находится в точке 1. Если лягушка не может добраться домой, то выведите -1.
Выходные данные
Если лягушка не сможет попасть домой, выведите -1.
В противном случае, выведите минимальное количество прыжков, которые нужно сделать лягушке, чтобы попасть из точки 1 в точку n.
Примечание
В первом примере лягушка может добраться до дома за два прыжка: первый прыжок из точки 1 в точку 4 (длина прыжка равна трём), а второй прыжок из точки 4 в точку 8 (длина прыжка равна четырём).
Во втором примере лягушка не сможет добраться до дома, так как ей нужно для этого прыгнуть на расстояние три, а максимальная длина её прыжка равна двум.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
8 4
10010101
|
2
|
|
2
|
4 2
1001
|
-1
|
|
3
|
8 4
11100101
|
3
|
|
4
|
12 3
101111100101
|
4
|