Indian National Olympiad in Informatics

Online Programming Contest, 15-16 July 2006

IARCS home > OLYMPIAD

Basic Division

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:

  1. No player may play more than two games.
  2. No player can play more than one game with the same colour.
  3. 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