Intr-o frumoasa zi de toamna Radu si Mars au observat ca aleea din gradina in
care obisnuiesc sa se recreeze, e cam plina de frunze. S-au hotarat sa stranga
toate frunzele in fix K gramezi.
Aleea este in linie dreapta, iar ei si-au fixat un sistem de coordonate pe alee,
cu originea la inceputul aleii. Pe alee sunt N
frunze de diferite greutati, asezate linie, la distanta 1
una fata de alta. Mai exact, prima frunza se afla la coordonata 1,
a doua la coordonata 2, ... , a
N-a la coordonata N.
Initial cei doi se afla la coordonata N.
Operatia de strangere a frunzelor se intampla cand Radu si Mars pleaca din gradina,
asa incat frunzele pot fi mutate doar spre stanga. Costul mutarii unei
frunze este egal cu greutatea sa inmultita cu distanta pe care este mutata. Evident
una dintre cele K gramezi va fi
formata la coordonata 1, insa restul
pot fi oriunde.
Cerinta
Aflati care este costul
total minim pentru a strange cele N
frunze in fix K gramezi.
Date de
intrare
In fisierul leaves.in se afla pe
prima linie doua numere naturale N
si K, separate de un spatiu, cu
semnificatia din enunt. Pe urmatoarele N
linii se afla N
numere naturale reprezentand greutatile frunzelor (pe linia i+1
se afla greutatea frunzei situate la coordonata i).
Date
de iesire
Fisierul
de iesire leaves.out va contine
o singura linie pe care va fi scris costul minim pentru strangerea tuturor frunzelor
in fix K gramezi.
Restrictii
0 < N < 100 001
0
< K < 11, K < N
0
< greutatea oricarei frunze < 1
001
Exemplu
leaves.in
leaves.out
Explicatii
5 2 1 2 3
4 5
13
Cel
mai bine e sa formam cele 2 gramezi
in punctele 1 si 4.
Frunzele 1, 2
si 3 se aduc in punctul de coordonata
1, iar 4
si 5 se aduc in punctul de coordonata
4. Costul total este:
1 * 0 + 2 * 1 + 3 * 2 + 4 * 0 + 5 * 1
= 13