AT_joi2018ho_a ストーブ (Stove)

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 翻译