- Time limit: 1.00 s
- Memory limit: 512 MB
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}$
- $2 \le n \le 2 \cdot 10^{5}$
- $1 \le x_i \le 1000$
- $2 \le n \le 2 \cdot 10^{5}$
- $1 \le x_i \le 10^{9}$