z-paradajz

Mali Z je resio da zivi zdravim zivotom, pa je odlucio da svaki dan pojede po jedan paradajz.<br><br>

Kako cena paradajza varira vremenom, mali Z je otisao kod prorocice da sazna cene paradajza u narednih n dana. Mali Z zeli da ustedi novac tako sto ce kupovati paradajz na najoptimalniji nacin, ali pri tome mora da pazi da se paradajz ne pokvari. Tacnije, paradajz kupljen i-tog dana je zdrav do (i+d-1)-vog dana. Znaci zivotni vek paradajza je d. *Napomena: Z moze kupiti koliko god oce paradajza jednog dana!<br><br>

Vas zadatak je da za zadate informacije o cenama paradajza u narednih n dana, kao i zivotni vek paradajza d, izracunate minimalnu sumu novca sa kojom mali Z moze da pojede po jedan paradajz SVAKI dan.<br><br>

Ulaz:<br><br>
Sa standardnog ulaza se u prvoj liniji ucitavaju dva broja, n i d. 1 <= n, d <= 200000, pri cemu je d <= n. U narednih n linija se ucitavaju cene paradajza Ci (i = 1..n), pri cemu je maksimalna cena paradajza 1000.<br><br>

Izlaz:<br><br>
Na standardni izlaz treba ispisati samo jedan broj, a to je minimalna suma novca potrebnog malom Z-u da svaki dan pojede po jedan paradajz.<br><br>

Primer:<br><br>
Ulaz:<br>
8 3<br>
1<br>
2<br>
3<br>
2<br>
4<br>
1<br>
3<br>
2<br><br>
Izlaz:<br>
10<br><br>

Objasnjenje:<br>
Mali Z ce kupiti 3 paradajza 1. dana, zatim 2 paradajza 4. dana, i konacno 3 paradajza 6. dana.
<br><br>
Napomena:<br>
Mali Z moze pojesti paradajz istog dana kada ga je i kupio.