Perica je oduvek voleo igre na sreću, pa je smislio jednu za svog druga Jovicu. Perica
uzme n papirića, na svakom papiriću napiše po jedan broj i okrene ih tako da Jovica ne
zna koji su brojevi napisani. Zatim Jovica mora da rasporedi sve papiriće na proizvoljan
broj gomila. Svaka gomila mora da ima najmanje 2, a najviše k papirića. Na kraju Perica
otkrije sve papiriće, te računa broj poena koji je Jovica osvojio.
Perica računa poene na sledeći način: Pronađe najveći i najmanji broj na jednoj gomili
i izračuna njihovu razliku. Kada izračuna razliku najvećeg i najmanjeg za svaku gomilu,
sabere sve razlike. Dobijena vrednost predstavlja osvojene poene. Što je broj poena manji,
to je Jovica uspešniji.
Znajući koje brojeve je Perica napisao na papiriće, odredite koliko najmanje poena
Jovica može da sakupi.
Ulaz:
(Ulazni podaci se učitavaju iz datoteke papirici.in.)
U prvom redu ulaza nalaze se dva broja n i k (2 ≤ k ≤ n ≤ 100.000)
koji predstavljaju, redom, broj papirića i maksimalnu
veličinu gomila. U drugom redu se nalazi n celih brojeva, koji predstavljaju brojeve
napisane na papirićima. Svi brojevi će biti u intervalu [-231, 231 - 1].
Izlaz:
(Izlazni podaci se ispisuju u datoteku papirici.out.) U prvom i jedinom redu
izlaza ispisati najmanji broj poena koji može da se sakupi. Rešenje će uvek postojati.
Primer:
papirici.in
|
|
papirici.out
|
7 3
6 0 5 2 8 0 -2
|
|
7
|
Objašnjenje.
Na prvu gomilu se stave papirići sa brojevima 0 i 2, na drugu gomilu papirići sa 6, 5 i 8, a na
treću papirići sa 0 i -2. Ukupan broj poena je (2 - 0) + (8 - 5) +
(0 - (-2)) = 7
Napomena.
U 30% test primera biće k ≤ 100.