题目描述

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

输入格式

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

输出格式

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

3 2
1
3
6

4

3 1
1
2
6

6

3 3
1
3
6

3

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

12

提示

数据规模与约定

对于 $100 \%$ 的数据，$1 \leq N \leq 10^5$，$1 \leq K \leq N$，$1 \leq T_i \leq 10^9$（$1 \leq i \leq N$），$T_i < T_{i+1}$（$1 \leq i \leq N-1$）。

• Subtask $1$（$20$ points）：$N \leq 20$。
• Subtask $2$（$30$ points）：$N \leq 5000$。
• Subtask $3$（$50$ points）：没有额外的限制。

样例说明

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

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

由于炉子的总运行时间不能小于 $4$，输出 $4$。
对于样例 $2$：JOI 君只能打开一次炉子。因此，他在第一个客人来的时间 $1$ 打开炉子，当第三位客人离开时他在时间 $7$ 关掉炉子。
请注意，客人离开的时间可以与下一位客人到来的时间相同。
对于样例 $3$：JOI 君在每位客人到来时打开炉子，并在每位客人离开时关掉炉子。

题目说明：

来源于 The 17th Japanese Olympiad in Informatics (JOI 2017/2018) Final Round 的 T1：Stove。
由 @求学的企鹅 翻译整理。