JOI-kun 的房间里有一个火炉。由于 JOI-kun 已经习惯了寒冷，当他独自一人在房间时，不需要打开火炉。但是，当有客人来访时，他需要打开火炉。

某一天，将有 $N$ 位客人来访。第 $i$ 位客人（$1 \le i \le N$）将在时间 $T_i$ 到达，并在时间 $T_i + 1$ 离开。在任何时刻，最多只有一位客人访问 JOI-kun。

JOI-kun 可以随时打开或关闭火炉。每当他打开火炉时，都需要消耗一根火柴。JOI-kun 总共只有 $K$ 根火柴。因此，他最多只能打开火炉 $K$ 次。在一天开始时，火炉是关闭的。

当火炉开启时，需要消耗燃料。因此，JOI-kun 需要控制火炉的开关时间，他希望最小化火炉的总运行时间。

题目描述

给定客人来访的数据以及 JOI-kun 拥有的火柴数量，编写一个程序来计算火炉总运行时间的最小值。

输入格式

从标准输入读取以下数据：

• 第一行包含两个空格分隔的整数 $N, K$。这表示有 $N$ 位客人将访问 JOI-kun，且 JOI-kun 拥有 $K$ 根火柴。
• 接下来的 $N$ 行中的第 $i$ 行（$1 \le i \le N$）包含一个整数 $T_i$。这表示第 $i$ 位客人将在时间 $T_i$ 到达，并在时间 $T_i + 1$ 离开。

输出格式

输出一行到标准输出。该行应包含火炉总运行时间的最小值。

数据范围

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

• $1 \le N \le 100\,000$。
• $1 \le K \le N$。
• $1 \le T_i \le 1\,000\,000\,000$ ($1 \le i \le N$)。
• $T_i < T_{i+1}$ ($1 \le i \le N - 1$)。

子任务

子任务 1 [20 分]

满足以下条件： $N \le 20$。 $1 \le T_i \le 20$ ($1 \le i \le N$)。

子任务 2 [30 分]

• $N \le 5000$。

子任务 3 [50 分]

• 无附加限制。

样例

样例输入 1

3 2
1
3
6

样例输出 1

4

说明 1

在此样例中，有三位客人来访。如果他按以下方式开关火炉，则火炉在客人来访时开启，他总共打开了两次火炉，总运行时间为 $(4 - 1) + (7 - 6) = 4$。

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

样例输入 2

3 1
1
2
6

样例输出 2

6

说明 2

在此样例中，JOI-kun 只能打开火炉一次。因此，他在第一位客人到达时（时间 1）打开火炉，并在第三位客人离开时（时间 7）关闭火炉。 注意，客人离开的时间可能与下一位客人到达的时间相同。

样例输入 3

3 3
1
3
6

样例输出 3

3

说明 3

在此样例中，JOI-kun 在每位客人到达时打开火炉，并在每位客人离开时关闭火炉。

样例输入 4

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

样例输出 4

12