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