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.