题目描述

小明的房间里有一个炉子。因为 小明已经习惯了寒冷的温度，所以当他一个人在房间里时，他不需要打开炉子。但是，有客人时，他需要打开炉子。有一天，$N$ 位客人将拜访 小明。第 $i$ 个客人 ($1 \leq i \leq N$) 将在时间 $T_i$ 到达，并在时间 $T_i+1$ 离开。任何时间最多有一个客人访问 小明。小明可以随时开火或关火。小明用火柴打开炉子。小明只有 $K$ 根火柴。 因此他最多可以打开炉子 $K$ 次。在一天的开始，炉子是关闭的。当炉子打开时，它需要燃料。因此，小明控制着他何时打开或关闭炉子，他想尽量减少炉子的总运行时间。
现给定访问 小明的客人数据和 小明拥有的火柴数，请编写一个程序来计算炉子总运行时间的最小值。

输入格式

第一行包含两个空格分隔的整数 $N$，$K$。 这意味着 $N$ 位客人将访问 小明，而 小明 有 $K$ 根火柴。接下来的下 $N$ 行的第 $i$ 行包含整数 $T_i$。这意味着第 $i$ 个客人将在时间 $T_i$ 到达，并在时间 $T_i+1$ 离开。

输出格式

输出一行应包含一个整数为炉子总运行时间的最小值。

输入输出样例 #1

输入 #1

3 2
1
3
6

输出 #1

4

三位客人将访问 小明。如果他按以下方式打开和关闭炉子，那么当客人来访时打开炉子，他打开炉子两次，炉子的总运行时间为 $(4-1)+(7-6)=4$。

• 当第一位客人到来时，他在时间 1 打开炉子。
• 当第二位客人离开时，他在时间 4 关掉炉子。
• 当第三位客人到来时，他在时间 6 打开炉子。
• 当第三位客人离开时，他在时间 7 关掉炉子。

由于炉子的总运行时间不能小于 $4$，输出 $4$。

输入输出样例 #2

输入 #2

3 1
1
2
6

输出 #2

6

小明只能打开一次炉子。因此，他在第一个客人来的时间 $1$ 打开炉子，当第三位客人离开时他在时间 $7$ 关掉炉子。
请注意，客人离开的时间可以与下一位客人到来的时间相同。

输入输出样例 #3

输入 #3

3 3
1
3
6

输出 #3

3

输入输出样例 #4

输入 #4

10 5
1
2
5
6
8
11
13
15
16
20

输出 #4

12

小明在每位客人到来时打开炉子，并在每位客人离开时关掉炉子。

数据范围

对于所有输入数据，有 $1≤N≤10^5$，$1≤K≤N$，$1≤T_i≤10^9$ $(1≤i≤N)$，$T_i<T_{i+1}$ $(1≤i≤N-1)$。

大样例下载

百度网盘大样例下载 提取码: GFOI

阿里云盘大样例下载

夸克云盘大样例下载