User's AC Ratio

70.0% (7/10)

Submission's AC Ratio

41.2% (7/17)

Description

$22/7$ 是一個常見的 $\pi$ 近似值,這個近似值從古代就有人使用。縱使阿基米德並非這個近似值的始創者,但他證明了 $22/7$ 高估了圓周率。他以 $22/7$ 大於外切正 $96$ 邊形的周界作證明。
但是今天沒有要教你算圓周率,因為那出題太麻煩了。
人與人之間偶有嫌隙,但破鏡重圓才是正確的道路。
現在有一些人,他們形成一個朋友鏈(就直直一條沒有分支),可是他們之間有一些人吵架了,導致這個朋友鏈瀕臨斷裂,好消息是現在有一個新的科技繩可以把吵架的人綁在一起,這樣他們就重新和好了,可是這種繩子最多只能用 $k$ 條且為相同長度的,不然朋友鏈就會斷掉,而且單條越長越貴,所以要盡可能用短的繩子,已知綁起兩個人需要使用兩單位的繩子,三個人需要使用三單位的繩子,以此類推。想請問你繩子單條最短最少需要多長。

Input Format

第一行輸入包含三個正整數 $n$ $m$ $k$ ($2 \leq n \leq 10^ 9$, $m < n$ 且 $m \leq 10^ 6$, $k\leq m$)
代表有 $n$ 個人,編號從 $1$ 開始,還有 $m$ 個吵架,最多可以用 $k$ 段繩子。
第二行輸入包含 $m$ 個由小到大的整數用空白分開,第 $i$ 個代表編號第 $A_i$ 與 $A_i + 1$ 吵架

Output Format

輸出僅包含一個整數,代表答案。

Sample Input 1

100 5 2
20 26 30 75 80

Sample Output 1

12
// 將 $20\sim31$ 號綁在一起需要 $12$ 單位的繩子,將 $75\sim81$ 號綁在一起需要 $7$ 單位的繩子
// 每條繩子最少需要 $12$ 單位才能破鏡重圓重修舊好

Hints

Problem Source

Subtasks

No. Testdata Range Score
1 0~12 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 2000 65536 65536 1
7 1000 65536 65536 1
8 2000 65536 65536 1
9 2000 65536 65536 1
10 2000 65536 65536 1
11 2000 65536 65536 1
12 1000 65536 65536 1