eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Одноразові камені

Одноразові камені

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB

Багато жаб хочуть потрапити на той бік річки. Річка має ширину w, але жаби можуть стрибати на відстань не більше l, причому l < w. На щастя, в річці є камені, які можуть допомогти потрапити на той бік.

Камені знаходяться на цілих відстанях від берегів. На відстані i від берега, на якому зараз знаходяться жаби, знаходиться a[i] каменів. Кожний камінь може бути використаний тільки однією жабою, після чого він тоне.Яка максимальна кількість жаб може потрапити на той бік річки, якщо вони можуть лише стрибати по каменям?

Вхідні дані

Перший рядок містить два цілих числа w і l (1 ≤ l < w ≤ 10^5) – ширина річки і максимальний розмір стрибка жаби.

Другий рядок містить w-1 цілих чисел a[1], a[2] ... a[(w-1)] (0 ≤ a[i]10^4) – кількість каменів на відповідній відстані.

Вихідні дані

Виведіть одне число – максимальну кількість жаб, які можуть потрапити на той бік.

Приклад

Вхідні дані #1
10 5
0 0 1 0 2 0 0 1 0
Вихідні дані #1
3
Вхідні дані #2
10 3
1 1 1 1 2 1 1 1 1
Вихідні дані #2
3