Cerința
Muncitorul Zen are de urcat N
trepte. Pentru a călca pe o treaptă i
, acesta trebuie să plătească o sumă C[i]
. Fiind un tip sportiv, acesta poate ajunge pe treapta i
de pe treptele i-1, i-2, ..., i-K
. Știind că acesta se află inițial la baza scării (pe treapta 0
, cu C[0] = 0
), se întreabă care este suma totală minimă pe care Zen trebuie să o plătească să ajungă pe treapta N
.
Date de intrare
Fișierul de intrare zen.in
conține pe prima linie numerele N
și K
, iar pe a doua linie N
numere naturale separate prin spații, al i
-lea reprezentând costul C[i]
.
Date de ieșire
Fișierul de ieșire zen.out
va conține pe prima linie numărul S
, reprezentând suma totală minimă pe care Zen trebuie să o plătească să ajungă pe treapta N
.
Restricții și precizări
1 ≤ N,K ≤ 1.000.000
1 ≤ C[i] ≤ 10.000
Exemplu:
zen.in
6 3 4 3 2 5 6 4
zen.out
6
Explicație
Zen sare pe treapta 3
apoi pe treapta 6
.