该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

有一根长度为 $L$ 厘米的年糕。年糕上有 $N$ 个切痕标记，从左数第 $i$ 个切痕位于左端开始的 $A_i$ 厘米处。

你需要从这 $N$ 个切痕中选择 $K$ 个下刀，将年糕分成 $K+1$ 段。定义分数为：$K+1$ 段年糕中最短一段的长度（单位：厘米）。

请求出在使分数最大的切割方案下，能够获得的分数值。

约束条件

• $1 ≤ K ≤ N ≤ 100000$

• $0 < A_1 < A_2 < ⋯ < A_N < L ≤ 10^9$

• 所有输入均为整数

提示：注意可能会出现超出int表示范围。

输入格式

第一行包含三个整数 $N$ ， $L$ 和 $K$ 分别表示切痕标记个数，年糕的长度和能下刀的个数。

第二行包含 $n$ 个整数 —— 数组 $A$。

输出格式

请输出所求的分数。

样例

3 34
1
8 13 26

13

7 45
2
7 11 16 20 28 34 38

12

3 100
1
28 54 81

46

3 100
2
28 54 81

26

20 1000
4
51 69 102 127 233 295 350 388 417 466 469 523 553 587 720 739 801 855 926 954

170