2752: B.自习室
题目描述
临近期末考试，自习室的学生来来往往。
这可忙坏了管理自习室的大爷，他随时准备开关灯。
自习室只要有学生来，就需要开灯。 一开始没有学生来之前灯是关闭的。
周日这一天共有 n 位同学来自习，第 i 个同学将在时间 Ti 来自习室，并在时间 Ti ＋ 1 离开。
按照规定任何时间最多一个同学在自习室（防止同学之间说话影响学习）。
大爷可以随时开灯和关灯（有学生在自习室的时候不能关灯）。
由于学生频繁出入，大爷已经厌倦了每天反复开关灯，所以他决定一天最多开灯 k 次，当然他想尽量减 少灯亮的时间（节约用电）。
请计算这一天灯亮时间的最小值。
输入
第一行包含两个空格分隔的整数 n ,k。
接下来 n 行,第 i 行包含整数 Ti，表示第 i 个学生将在时间 Ti 到达自习室，并在时间 Ti + 1 离开自习 室。
输出
一行包含一个整数为灯亮时间的最小值。
样例输入 复制
3 2
2
4
8样例输出 复制
4提示
样例1说明：
第1个同学来时，第2时刻开灯；
第2位同学离开时，第5时刻关灯；
第3位同学来时，第8时刻开灯；
第3位同学离开时，第9时刻关灯。
灯亮的时间是（5-2）+（ 9-8）=4.
样例 #2
样例输入 #2
|
3 1
2
4
6
|
样例输出 #2
|
5
|
样例 #3
样例输入 #3
|
3 3
1
3
6
|
样例输出 #3
3
样例输入 #4
10 5
1
2
5
6
8
11
13
15
16
20
样例输出 #4
12
数据规模与约定
所有 的数据， 1 ≤ n ≤ 105，1 ≤ k ≤ n，1 ≤Ti ≤ 109 （1 ≤ i ≤ n ），Ti ＜Ti+1 (1 ≤ i ≤ n-1) 。
对于20% 的数据： n≤20。
对于30% 的数据： n≤5000。
对于50% 的数据：没有额外的限制。