Koodarit

• Time limit: 1.00 s
• Memory limit: 512 MB

Yrityksessä on $n$ koodaria, joista jokaisella on tietty taitotaso. Koodareista halutaan muodostaa $k$ paria niin, että taitotasot ovat lähellä toisiaan.

Kun parissa olevien koodarien taitotasot ovat $a$ ja $b$, tästä tulee sakkoa $|a-b|$. Ratkaisun kokonaissakko on kaikkien parien sakkojen summa.

Tehtäväsi on selvittää, mikä on pienin mahdollinen ratkaisun kokonaissakko.

Syöte

Syötteen ensimmäisellä rivillä on kokonaisluvut $n$ ja $k$: koodarien määrä ja parien määrä. Kaikissa testeissä pätee $1 \leq k \leq n/2$.

Seuraavalla rivillä on $n$ kokonaislukua $x_1,x_2,\dots,x_n$: jokaisen koodarin taitotaso.

Tuloste

Tulosta yksi kokonaisluku: pienin mahdollinen kokonaissakko.

Esimerkki

Syöte:
8 3
3 1 2 7 9 3 4 7

Tuloste:
1

Selitys: Voidaan valita parit $(1,2)$, $(3,3)$ ja $(7,7)$.

Osatehtävä 1 (34 pistettä)

• $2 \le n \le 2000$
  
• $1 \le x_i \le 10^{9}$
  

Osatehtävä 2 (21 pistettä)

• $2 \le n \le 2 \cdot 10^{5}$
  
• $1 \le x_i \le 1000$
  

Osatehtävä 3 (45 pistettä)

• $2 \le n \le 2 \cdot 10^{5}$
  
• $1 \le x_i \le 10^{9}$