Problem 2: Chess Festival, *(K Narayan Kumar, CMI)*

The Siruseri Chess Club has decided to hold a Festival of
Chess to attract youngsters to take up the game. There
are *N* chess players in Siruseri and the Club knows the
ELO rating of each player. You may assume that no two players
have the same ELO rating. The Club has decided to
organize *K* matches, where *K* < *N*,
satisfying the following rules:

- No player may play more than two games.
- No player can play more than one game with the same colour.
- In all games, the player with the higher ELO rating will play with black.

In order to the make the matches as close as possible, it has
been decided to organize the *K* games so that the sum of
the (absolute values of the) differences in ELO ratings between
the players is as small as possible.

Your task is to help the Siruseri Chess Club to choose the
pairings for the matches based on the ELO ratings of
the *N* players and the number of games, *K*, to be
played.

For example, suppose there are 7 players with ratings 30, 17, 26,
41, 19, 38 and 18, and *K* = 3. Then, the best pairings
would be: Player 2 vs Player 7, Player 7 vs Player 5 and finally
Player 6 vs Player 4, for a total sum of (18-17) + (19-18) +
(41-38) = 5.

Input format

The first line contains two integers *N*
and *K*. This is followed by *N* lines containing
the ELO ratings of the *N* players.

Output format

A single integer giving the minimum sum of differences possible for the
*K* games, meeting the requirements listed above.

Test data

You may assume that *N* ≤ 100000 and *K* <
*N*. In 90% of the
inputs, *N* ≤ 3000.

Example

Here is a sample input and output corresponding to the example discussed above.

Sample input

7 3 30 17 26 41 19 38 18

Sample output

5

Copyright (c) IARCS 2003-2018; Last Updated: 03 Sep 2006