CSES - Datatähti 2021 loppu - 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}$