Много лягушек хотят пересечь реку. Река имеет ширину $$$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$$$.
Название |
---|