B. Обогреватели
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дом Вовы представляет собой массив, состоящий из $$$n$$$ элементов (да, я думаю, это первая задача, в которой кто-то живет в массиве). В некоторых позициях массива расположены обогреватели. $$$i$$$-й элемент массива равен $$$1$$$, если в позиции $$$i$$$ находится обогреватель, иначе $$$i$$$-й элемент массива равен $$$0$$$.

Каждый обогреватель имеет характеристику $$$r$$$ ($$$r$$$ одинаково для всех обогревателей). Эта характеристика значит, что обогреватель в позиции $$$pos$$$ может обогревать все элементы в отрезке $$$[pos - r + 1; pos + r - 1]$$$.

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

Цель Вовы — обогреть весь дом (все элементы массива), то есть если $$$n = 6$$$, $$$r = 2$$$ и обогреватели находятся в позициях $$$2$$$ и $$$5$$$, тогда Вова может обогреть весь дом, если он включит все обогреватели в доме (тогда первые $$$3$$$ элемента будет обогревать первый обогреватель, а последние $$$3$$$ элемента будет обогревать второй обогреватель).

Изначально все обогреватели выключены.

Но с другой стороны Вова не любит очень много платить за электричество. Итак, он хочет включить минимальное количество обогревателей таким образом, что каждый элемент его дома будет обогреваться хотя бы одним из обогревателей.

Ваша задача — найти это количество обогревателей или сказать, что невозможно обогреть весь дом.

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

Первая строка входных данных содержит два целых числа $$$n$$$ и $$$r$$$ ($$$1 \le n, r \le 1000$$$) — количество элементов в массиве и характеристика обогревателей.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 1$$$) — описание дома Вовы.

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

Выведите одно целое число — минимальное количество обогревателей, которые необходимо включить, чтобы обогреть весь дом, или -1, если это невозможно сделать.

Примеры
Входные данные
6 2
0 1 1 0 0 1
Выходные данные
3
Входные данные
5 3
1 0 0 0 1
Выходные данные
2
Входные данные
5 10
0 0 0 0 0
Выходные данные
-1
Входные данные
10 3
0 0 1 1 0 1 0 0 0 1
Выходные данные
3
Примечание

В первом тестовом примере обогреватель в позиции $$$2$$$ обогревает элементы $$$[1; 3]$$$, обогреватель на позиции $$$3$$$ обогревает точки $$$[2, 4]$$$ и обогреватель на позиции $$$6$$$ обогревает точки $$$[5; 6]$$$, таким образом ответ равен $$$3$$$.

Во втором тестовом примере обогреватель в позиции $$$1$$$ обогревает элементы $$$[1; 3]$$$ и обогреватель на позиции $$$5$$$ обогревает точки $$$[3; 5]$$$, таким образом ответ равен $$$2$$$.

В третьем тестовом примере нет обогревателей, таким образом ответ равен -1.

В четвертом тестовом примере обогреватель в позиции $$$3$$$ обогревает элементы $$$[1; 5]$$$, обогреватель в позиции $$$6$$$ обогревает элементы $$$[4; 8]$$$ и обогреватель в позиции $$$10$$$ обогревает элементы $$$[8; 10]$$$, таким образом ответ равен $$$3$$$.