题目描述

翁老师 的房间里有一个炉子。因为 翁老师 已经习惯了寒冷的温度，所以当他一个人在房间里时，他不需要打开炉子。但是，有客人时，他需要打开炉子。有一天，$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$ 离开。

输出格式

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

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$）。

本题采用捆绑测试

样例 1 解释

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

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

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

样例 2 解释

翁老师只能打开一次炉子。因此，他在第一个客人来的时间 $1$ 打开炉子，当第三位客人离开时他在时间 $7$ 关掉炉子。

请注意，客人离开的时间可以与下一位客人到来的时间相同。

样例 3 解释

翁老师在每位客人到来时打开炉子，并在每位客人离开时关掉炉子。