Много лягушек хотят пересечь реку. Река имеет ширину \(w\), но лягушки могут прыгать только на расстояние \(l\), причём \(l < w\). Кроме того, лягушки могут прыгать на расстояния, меньшие \(l\), но не на расстояния большие. К счастью, в реке есть камни, которые могут помочь пересечь реку.
Камни расположены на целых расстояниях от берегов. На расстоянии \(i\) от берега, на котором сейчас находятся лягушки, находится \(a_i\) камней. Каждый камень может быть использован только одной лягушкой, после чего он тонет.
Какое максимальное количество лягушек может пересечь реку, если они могут прыгать только по камням?
Выходные данные
Выведите одно целое число — максимальное количество лягушек, которые могут пересечь реку.
Примечание
В первом примере две лягушки могут использовать два разных камня на расстоянии \(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\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
10 5
0 0 1 0 2 0 0 1 0
|
3
|
|
2
|
10 3
1 1 1 1 2 1 1 1 1
|
3
|