CSES - Koodarit
  • Time limit: 1.00 s
  • Memory limit: 512 MB

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

Kun parissa olevien koodarien taitotasot ovat aa ja bb, tästä tulee sakkoa ab|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 nn ja kk: koodarien määrä ja parien määrä. Kaikissa testeissä pätee 1kn/21 \leq k \leq n/2.

Seuraavalla rivillä on nn kokonaislukua x1,x2,,xnx_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)(1,2), (3,3)(3,3) ja (7,7)(7,7).

Osatehtävä 1 (34 pistettä)

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

Osatehtävä 2 (21 pistettä)

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

Osatehtävä 3 (45 pistettä)

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