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 ≤ 1.000.000
• 1 ≤ K ≤ 10.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.