Станция
Тайвань имеет железнодорожную систему, соединяющую все станции. Станции пронумерованы от 0 до n - 1. Расстояние между каждыми соседними станциями составляет 1 километр, на некоторых станциях можно переночевать. На первой и последней станции можно устроиться на ночевку.
Джан-Джи хочет попутешествовать по Тайваню по имеющейся железнодорожной системе. Джан-Джи начнет свой путь с начальной станции и закончит в последней. Так как Джан-Джи имеет билет со скидкой, он может проезжать не более k километров за один день. Останавливаться на ночевку Джан-Джи хочет только на тех станциях, где это возможно. Определите наименьшее количество дней, за которое Джан-Джи сможет проехать с начальной станции до последней.
Имеется информация, где на станциях можно переночевать, а также ограничение k. Определите, сможет ли Джан-Джи проехать с начальной станции до конечной. И если ответ положительный, то выведите наименьшее количество дней, за которое он сможет это сделать.
Входные данные
Первая строка содержит два числа n (2 ≤ n ≤ 5 * 10^5) и k (1 ≤ k ≤ 3000). Вторая строка содержит массив lodge указывающий можно ли на станции переночевать. Так, если на станции можно устроиться на ночевку, то lodge[i] равно 1, и 0 иначе. Оба значения lodge[0] и lodge[n-1] равны 1.
Выходные данные
Вывести наименьшее количество дней, за которое Джан-Джи сможет доехать с начальной станции до конечной. Если такую поездку совершить невозможно, то вывести -1.
Пример
Рассмотрим третий тест. Имеется 10 станций, а на станциях 0, 1, 2, 3, 4, 6, 7, 9 можно переночевать. Значение k равно 4, то есть Джан-Джи может путешествовать не более 4 километра в день. Тогда ему надо как минимум 3 дня чтобы добраться со станции 0 до станции 9. Например, он может проехать со станции 0 до станции 3 в первый день, со станции 3 до 7 во второй день, и со станции 7 до 9 в третий день. Если k равно 1, то совершить путешествие с начальной станции до конечной невозможно.
