leaves

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.

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).

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.

• 0 < N < 100 001
• 0 < K < 11, K < N
• 0 < greutatea oricarei frunze < 1 001

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