CF1110B Tape

你有一根长棍，由 $m$ 个段组成，编号从 $1$ 到 $m$。每个段长 $1$ 厘米。不幸的是，其中一些段已经损坏，需要修复。 你有一卷无限长的修复胶带。你可以从胶带上剪下一些长度为整数的胶带，用来覆盖所有损坏的段。具体来说，长度为 $t$ 的一段胶带，放在位置 $s$ 上时，会覆盖第 $s, s+1, \ldots, s+t-1$ 段。 你可以覆盖未损坏的段；也允许胶带之间有重叠。 时间就是金钱，所以你最多只能剪下 $k$ 段连续的胶带来覆盖所有损坏的段。请问这些胶带的最小总长度是多少？

第一行包含三个整数 $n$、$m$ 和 $k$（$1 \le n \le 10^5$，$n \le m \le 10^9$，$1 \le k \le n$），分别表示损坏的段数、棍子的长度和你最多可以使用的胶带段数。 第二行包含 $n$ 个整数 $b_1, b_2, \ldots, b_n$（$1 \le b_i \le m$），表示损坏段的位置。这些整数按递增顺序给出，即 $b_1 < b_2 < \ldots < b_n$。

输出这些胶带段的最小总长度。

在第一个样例中，你可以用一段长度为 $11$ 的胶带覆盖损坏的第 $20$ 段和第 $30$ 段，再用一段长度为 $6$ 的胶带覆盖第 $75$ 段和第 $80$ 段，总长度为 $17$。 在第二个样例中，你可以用一段长度为 $4$ 的胶带覆盖损坏的第 $1$、$2$ 和 $4$ 段，再用两段长度为 $1$ 的胶带分别覆盖第 $60$ 和第 $87$ 段。 由 ChatGPT 4.1 翻译