Tien varrella on n taloa, ja tiedät jokaisesta talosta, montako lasta siinä asuu. Tehtäväsi on perustaa k koulua niin, että jokainen koulu on jossakin talossa ja lasten yhteismatka kouluun on mahdollisimman lyhyt.

Syöte

Syötteen ensimmäisellä rivillä on kaksi kokonaislukua n ja k: talojen määrä ja koulujen määrä. Talot on numeroitu 1,2,\ldots,n.

Sitten syötteessä on n kokonaislukua t_1,t_2,\ldots,t_n: montako lasta kussakin talossa asuu.

Koulujen perustamisen jälkeen kaikki tietyssä talossa asuvat lapset menevät lähimpään kouluun. Matkan kustannus on lasta kohden |a-b|, missä a on talon numero ja b on koulun numero.

Tuloste

Tulosta yksi kokonaisluku: pienin mahdollinen kaikkien lasten yhteiskoulumatka.

Rajat

• 1 \le n,k \le 5000
• 1 \le t_i \le 10^6

Esimerkki

Syöte:

6 2
2 7 1 4 6 4

Tuloste:

11

Selitys: koulut perustetaan taloihin 2 ja 5.