← 返回题目列表

Codeforces · 1110/B

B. 胶带

中文机器翻译题面 查看原题

你有一根长棍子,由$$$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$$$。

输出

打印各片的最小总长度。

示例

输入 #1

4 100 2
20 30 75 80

输出 #1

17

输入 #2

5 100 3
1 2 4 60 87

输出 #2

6

注意

在第一个示例中,您可以使用一段长度 $$$11$$$ 来覆盖破损的段 $$$20$$$ 和 $$$30$$$,并使用另一段长度 $$$6$$$ 来覆盖 $$$75$$$ 和 $$$80$$$,总长度为 $$$17$$$。

在第二个示例中,您可以使用一段长度 $$$4$$$ 来覆盖损坏的段 $$$1$$$、$$$2$$$ 和 $$$4$$$,并使用两段长度 $$$1$$$ 来覆盖损坏的段 $$$60$$$ 和 $$$87$$$。