한 번만 사용할 수 있는 돌

많은 개구리가 강을 건너고 싶어 한다. 강의 폭은 w단위이지만, 개구리는 l < w인 경우 한 번에 최대 l단위 길이만큼만 뛸 수 있다. 개구리는 l보다 짧은 길이로도 뛸 수 있지만, 그보다 길게는 뛸 수 없다. 다행히도 강에는 개구리들을 도와줄 돌이 몇 개 있다.

돌은 강둑에서 정수 거리만큼 떨어진 곳에 있다. 개구리들이 현재 있는 강둑에서 i단위 떨어진 위치에는 $a_i$개의 돌이 있다. 각 돌은 한 마리의 개구리만 한 번 사용할 수 있으며, 사용된 뒤에는 물속으로 가라앉는다.

개구리들이 돌만 밟아 뛸 수 있을 때, 강을 건널 수 있는 개구리 수의 최댓값은 얼마인가?

첫 번째 줄에 두 정수 w와 l (1 ≤ l < w ≤ $10^5$)이 주어진다. 각각 강의 폭과 개구리가 한 번에 뛸 수 있는 최대 길이를 나타낸다.

두 번째 줄에 w - 1개의 정수 $a_1$, $a_2$, …, $a_{w-1}$ (0 ≤ $a_i$ ≤ $10^4$)이 주어진다. 여기서 $a_i$는 개구리들이 현재 있는 강둑에서 i만큼 떨어진 위치에 있는 돌의 수이다.

강을 건널 수 있는 개구리 수의 최댓값을 나타내는 정수 하나를 출력한다.

첫 번째 예제에서는 두 마리의 개구리가 거리 5에 있는 서로 다른 돌을 사용할 수 있고, 한 마리의 개구리는 거리 3에 있는 돌을 사용한 다음 거리 8에 있는 돌을 사용할 수 있다.

두 번째 예제에서는 거리 5에 돌이 두 개 있지만 도움이 되지 않는다. 세 경로는 다음과 같다: 0 → 3 → 6 → 9 → 10, 0 → 2 → 5 → 8 → 10, 0 → 1 → 4 → 7 → 10.