User's AC Ratio

100.0% (29/29)

Submission's AC Ratio

67.1% (53/79)

Description

你有很長很長的竹棒,總共有 $m$ 個竹節,因為這個竹子得了新型冠狀病毒,導致每一個竹節都一樣長。
小明是個很可惡的小屁孩,打 LOL 掛機、動嘴不動腦、罵人學店仔,這個大壞蛋對你的竹棒做了壞壞的事情,他拿打洞機在你的竹節上面打洞,你快要氣瘋了。
十分喜愛棒棒的你,決定用膠帶修復竹子,只要將膠帶貼上竹子表面就算修復完成,就算沒有被打洞的竹節也可以被貼膠帶。
小明總共傷害棒棒共 $n$ 個竹節,但是你只想用至多 $k$ 段膠帶修復棒棒,請問最少要使用多長的的膠帶才能修復這根棒棒?
竹棒總共有 $m$ 節,從 $1$ 開始編號到 $m$ 。

P.S. 每段膠帶長度可任意。

Input Format

第一行有三個整數 $n, m$, $k$ ($1\leq n\leq10^ 5, n\leq m\leq10^ 9, 1\leq k\leq n$) 分別代表被破壞的竹節個數、全部的竹節數量以及至多使用的膠帶段數。

第二行有 $n$ 個整數 ($b_1,b_2,\cdots,b_n$) ,代表被破壞的竹節是第幾節,且依序由小到大。($1\leq b_i\leq m, b_1<b_2<\cdots<b_n$)

Output Format

最短需要使用的膠帶總長度,單位為「竹節長」。

Sample Input 1

4 100 2
20 30 75 80

Sample Output 1

17

Sample Input 2

5 100 3
1 2 4 60 87

Sample Output 2

6

Hints

對於第一個範例,你會使用 $17$ 個竹節長的膠帶,分別貼在 $20\sim30$ ( $11$ 竹節長)之間與 $75\sim80$ ( $6$ 竹節長)之間。
對於第二個範例,你會使用 $6$ 個竹節長的膠帶,分別貼在 $1\sim4,60,87$ 。

Problem Source

Subtasks

No. Testdata Range Score
1 0~9 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 65536 65536 1
1 1000 65536 65536 1
2 1000 65536 65536 1
3 1000 65536 65536 1
4 1000 65536 65536 1
5 1000 65536 65536 1
6 1000 65536 65536 1
7 1000 65536 65536 1
8 1000 65536 65536 1
9 1000 65536 65536 1