Problem description


Kaktusy
(kaktusy)
Memory limit: 32 MB
Time limit: 2.00 s

Jasio wybrał się na pole kaktusowe. Pole to jest planszą wymiaru 1 × N. Na każdym polu znajduje się pewna liczba bardzo ostrych kaktusów. Jasio chce przebyć całą planszę (znajduje się przed pierwszym polem, a chciałby się znaleźć za ostatnim), niestety potrafi wykonać skok długości co najwyżej K pól. Ile minimalnie kaktusów musi zdeptać, aby przejść planszę?

Napisz program, który: wczyta opis planszy i maksymalny skok Jasia, wyznaczy minimalną liczbę kaktusów, na które Jasio musi się nadziać, aby przebyć planszę i wypisze wynik na standardowe wyjście.

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby naturalne N i K, oddzielone pojedynczym odstępem i określające kolejno: długość planszy oraz maksymalną długość skoku Jasia. W drugim (i ostatnim) wierszu wejścia znajduje się ciąg N liczb całkowitych Ai, pooddzielanych pojedynczymi odstępami. Określają one liczbę kaktusów na i-tym polu.

Wyjście

W pierwszym (i jedynym) wierszu wyjścia powinna się znaleźć jedna liczba całkowita – minimalna liczba kaktusów, w które musi wejść Jasio aby pokonać planszę.

Ograniczenia

1 ≤ N ≤ 500 000, 1 ≤ K ≤ 500 000, 0 ≤ Ai ≤ 109.

Przykład

Input Output Explanation
7 3
1 3 4 2 3 1 10
4

Jasio może na przykład: wskoczyć na pierwsze pole, następnie przeskoczyć na czwarte, a potem na szóste, by wreszcie przeskoczyć za ostatnie pole. Łącznie zdepcze wtedy 1 + 2 + 1 = 4 kaktusy.