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

Много лягушек хотят пересечь реку. Река имеет ширину $$$w$$$, но лягушки могут прыгать только на расстояние $$$l$$$, причём $$$l < w$$$. Кроме того, лягушки могут прыгать на расстояния, меньшие $$$l$$$, но не на расстояния большие. К счастью, в реке есть камни, которые могут помочь пересечь реку.

Камни расположены на целых расстояниях от берегов. На расстоянии $$$i$$$ от берега, на котором сейчас находятся лягушки, находится $$$a_i$$$ камней. Каждый камень может быть использован только одной лягушкой, после чего он тонет.

Какое максимальное количество лягушек может пересечь реку, если они могут прыгать только по камням?

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

Первая строка содержит два целых числа $$$w$$$ и $$$l$$$ ($$$1 \le l < w \le 10^5$$$) — ширина реки и максимальный размер прыжка лягушки.

Вторая строка содержит $$$w - 1$$$ целых чисел $$$a_1, a_2, \ldots, a_{w-1}$$$ ($$$0 \le a_i \le 10^4$$$), где $$$a_i$$$ — число камней на расстоянии $$$i$$$ от того берега, на котором изначально находятся лягушки.

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

Выведите одно целое число — максимальное количество лягушек, которые могут пересечь реку.

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

В первом примере две лягушки могут использовать два разных камня на расстоянии $$$5$$$, а ещё одна может использовать камни на расстояниях $$$3$$$ и $$$8$$$.

Во втором примере то, что на расстоянии $$$5$$$ находятся два разных камня, не улучшает ответ. Есть три разных пути: $$$0 \to 3 \to 6 \to 9 \to 10$$$, $$$0 \to 2 \to 5 \to 8 \to 10$$$, $$$0 \to 1 \to 4 \to 7 \to 10$$$.