JOI 君的房间里有一个取暖炉。由于 JOI 君本身不怕冷，所以当他一个人在房间时不需要开取暖炉，但有客人来访时就必须开取暖炉。

这一天，JOI 君将有 $N$ 位客人来访。第 $i$ 位客人（$1 \leq i \leq N$）会在时刻 $T_i$ 到达，并在时刻 $T_i + 1$ 离开。不会有多位客人在同一时刻到达。

JOI 君可以在任意时刻开关取暖炉。但每次开取暖炉都需要消耗一根火柴。JOI 君只有 $K$ 根火柴，因此最多只能开 $K$ 次取暖炉。一天开始时，取暖炉是关闭的。

由于取暖炉开启时会消耗燃料，JOI 君希望合理安排取暖炉的开关时机，使得取暖炉开启的总时间最小。

从标准输入读取以下内容。

• 第 $1$ 行包含两个整数 $N, K$，表示 JOI 君的房间有 $N$ 位客人来访，JOI 君有 $K$ 根火柴。
• 接下来的 $N$ 行中，第 $i$ 行（$1 \leq i \leq N$）包含一个整数 $T_i$，表示第 $i$ 位客人在时刻 $T_i$ 到达，并在时刻 $T_i + 1$ 离开。

输出一个整数，表示取暖炉开启的总时间的最小值。

任务

给定 JOI 君房间的来客信息和 JOI 君拥有的火柴数量，求取暖炉开启的总时间的最小值。

限制

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

• $1 \leq N \leq 100\,000$。
• $1 \leq K \leq N$。
• $1 \leq T_i \leq 1\,000\,000\,000$（$1 \leq i \leq N$）。
• $T_i < T_{i+1}$（$1 \leq i \leq N-1$）。

子任务

子任务 1 [20 分]

满足以下条件。

• $N \leq 20$。
• $1 \leq T_i \leq 20$（$1 \leq i \leq N$）。

子任务 2 [30 分]

• $N \leq 5\,000$。

子任务 3 [50 分]

• 无额外限制。

样例解释 1

在本输入样例中，JOI 君的房间有 $3$ 位客人来访。如下安排取暖炉的开关：

• 在第 $1$ 位客人到达的时刻 $1$ 开启取暖炉。
• 在第 $2$ 位客人离开的时刻 $4$ 关闭取暖炉。
• 在第 $3$ 位客人到达的时刻 $6$ 再次开启取暖炉。
• 在第 $3$ 位客人离开的时刻 $7$ 关闭取暖炉。

这样，取暖炉开启的总时间为 $(4-1)+(7-6)=4$，且开启次数为 $2$ 次。无法使开启总时间小于 $4$，因此输出 $4$。

样例解释 2

在本输入样例中，JOI 君只能开启一次取暖炉，因此可以在第 $1$ 位客人到达的时刻 $1$ 开启取暖炉，在第 $3$ 位客人离开的时刻 $7$ 关闭取暖炉。

需要注意的是，可能存在某位客人离开的时刻与下一位客人到达的时刻相同。

样例解释 3

在本输入样例中，JOI 君可以在每位客人到达时开启取暖炉，在每位客人离开时关闭取暖炉。

由 ChatGPT 4.1 翻译