Станція
Тайвань має залізничну систему, що з'єднує всі станції. Станції пронумеровані від 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, то здійснити подорож з початкової станції до кінцевої неможливо.
