JOI 君的房间

JOI 君的房间里有一个火炉。由于 JOI 君自己很能忍受寒冷，所以在独自一人的时候不需要开火炉。但是当有客人来访时，就需要开火炉。

今天，JOI 君的房间里有 N 个客人。第 i 个（1 ≤ i ≤ N）客人在时刻 Ti 到达，并在时刻 Ti + 1 离开。不会同时有多个客人。

JOI 君可以在任意时间开关火炉。但是，每次打开火炉都要消耗一根火柴。由于 JOI 君只有 K 根火柴，所以最多只能打开 K 次火炉。一天开始时，火炉是熄灭的。

开着火炉会消耗相应的燃料，所以需要恰当地确定开关火炉的时间，以最小化火炉开启的总时间。

任务

给定 JOI 君房间里客人的信息以及 JOI 君拥有的火柴数量，求火炉开启的总时间的最小值。

---

输入

从标准输入中读取以下输入：

• 第 1 行包含两个整数 N, K，以空格分隔。表示 JOI 君的房间里有 N 个客人，JOI 君有 K 根火柴。
• 接下来的 N 行中的第 i 行（1 ≤ i ≤ N）包含整数 Ti。表示第 i 个客人在时刻 Ti 到达并在时刻 Ti + 1 离开。

输出

将最小的火炉开启时间总和作为一行输出到标准输出中。

---

限制

所有输入数据满足以下条件：

• 1 ≤ N ≤ 100,000。
• 1 ≤ K ≤ N。
• 1 ≤ Ti ≤ 1,000,000,000 (1 ≤ i ≤ N)。
• Ti < Ti+1 (1 ≤ i ≤ N - 1)。

---

子任务

子任务 1 [20 分]

满足以下条件：

• N ≤ 20。
• 1 ≤ Ti ≤ 20 (1 ≤ i ≤ N)。

子任务 2 [30 分]

满足 N ≤ 5,000。

子任务 3 [50 分]

没有额外的限制。

---

示例输入 1

3 2
1
3
6

示例输出 1

4

在这个示例输入中，JOI 君的房间里有 3 个客人。按照以下方式打开和关闭火炉，客人到访时火炉是开着的，需要开火炉的次数为 2 次，总的火炉开启时间为（4 - 1）+ （7 - 6）= 4。

• 在第一个客人到达时间为 1 时打开火炉。
• 在第二个客人离开时间为 4 时关闭火炉。
• 在第三个客人到达时间为 6 时打开火炉。
• 在第三个客人离开时间为 7 时关闭火炉。

无法使总的火炉开启时间小于 4，因此答案为 4。

---

示例输入 2

3 1
1
2
6

示例输出 2

6

在这个示例输入中，JOI 君只能打开一次火炉，所以需要在第一个客人到达时间为 1 时打开火炉，在第三个客人离开时间为 7 时关闭火炉。

请注意，客人离开时间和下一个客人到达时间可能是一样的。

---

示例输入 3

3 3
1
3
6

示例输出 3

3

在这个示例输入中，JOI 君需要在每个客人到达时打开火炉，并在每个客人离开时关闭火炉。

---

示例输入 4

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

示例输出 4

12