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}