问题 23142 --Chess

23142: Chess

时间限制: 1 Sec  内存限制: 128 MB
提交: 38  解决: 34
[提交][状态][讨论版][命题人:]

题目描述

      有n个人要参加国际象棋比赛,该比赛要进行k场对弈。每个人最多参加两场对弈,最少参加零场对弈。每个人都有一个与其他人都不相同的等级(用一个正整数来表示)。在对弈中,等级高的人必须用黑色的棋子,等级低的人必须用白色的棋子。每个人最多只能用一次黑色的棋子和一次白色的棋子。为了增加比赛的客观度,观众希望k场对弈中上方的等级差的总和最小。比如有7个选手,他们的等级分别是30,17,26,41,19,38,18,要进行3场比赛。最好的安排是player 2 vs player 7, player 7 vs player 5, player 6 vs player 4,此时等级差的总和与(18-17)+(19-18)+(41-38)=5打到最小。


在90%的数据中,1≤n≤3000
在100%的数据中,1≤n≤100000
保证所有输入数据中等级的值小于108,1≤k≤n-1

输入

第一行两个正整数n,k。
接下来有n行,第i行表示第i-1和人等级。

输出

在第一行输出最小的等级差的总和。

样例输入

7 3
30
17
26
41
19
38
18

样例输出

5

来源

 

[提交][状态]