2405: 自习室

Memory Limit:128 MB Time Limit:1.000 S
Creator:
Submit:1 Solved:1

Description

临近期末考试,自习室的学生来来往往。这可忙坏了管理自习室的大爷,他随时准备开关灯。自习室只要有学生来,就需要开灯。一开始没有学生来之前灯是关闭的。
周日这一天共有 n 位同学来自习,第 i 个同学将在时间 Ti 来自习室,并在时间 Ti + 1离开。
按照规定任何时间最多一个同学在自习室(防止同学之间说话影响学习)。
大爷可以随时开灯和关灯(有学生在自习室的时候不能关灯)。
由于学生频繁出入,大爷已经厌倦了每天反复开关灯,所以他决定一天最多开灯 k 次,当然他想尽量减
少灯亮的时间(节约用电)。
请计算这一天灯亮时间的最小值

Input

第一行包含两个空格分隔的整数 n,k 。
接下来 行,第 n 行包含整数 ,表示第 i 个学生将在时间 Ti 到达自习室,并在Ti + 1时间离开自习室。

Output

一行包含一个整数为灯亮时间的最小值。

Sample Input

3 2
2
4
8

Sample Output

4

HINT

样例说明:
第1个同学来时,第2时刻开灯;
第2位同学离开时,第5时刻关灯;
第3位同学来时,第8时刻开灯;
第3位同学离开时,第9时刻关灯。
灯亮的时间是(5-2)+(9-8)=4.

所有的数据: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% 的数据:没有额外的限制。