跳石头

题目描述

Y 同学正在组织一年一度的“跳石头”比赛。

这项比赛将在一条笔直的河道中进行。河道的两端点分别设有起点和终点两块岩石，起点与终点之间的距离为 $L$。在这两块岩石之间，还分布着 $N$ 块岩石。在比赛过程中，选手们将从起点出发，依次跳向相邻的岩石，直至到达终点。

为了提高比赛难度，Y 同学计划移走一些岩石。由于预算和人力的限制，Y 同学至多只能从这 $N$ 块岩石中移走 $M$ 块（起点和终点的岩石固定不可移走）。Y 同学希望通过合理地选择被移走的岩石，使得选手们在比赛过程中的最短跳跃距离（即相邻两块岩石之间距离的最小值）尽可能大。

请你编写程序帮助 Y 同学计算出，在至多移走 $M$ 块岩石的前提下，最短跳跃距离的最大值。

输入格式

第一行包含三个整数 $L, N, M$，相邻两个整数之间由一个空格隔开，分别表示起点到终点的距离、起点与终点之间的岩石数量，以及最多可以移走的岩石数量。

接下来的 $N$ 行，每行包含一个整数 $D_i$，表示第 $i$ 块岩石到起点的距离。保证这些岩石按与起点距离严格单调递增的顺序给出，即 $0 < D_1 < D_2 < \dots < D_N < L$。

输出格式

输出一行一个整数，表示移走至多 $M$ 块岩石后，最短跳跃距离的最大值。

样例

样例输入 #1

25 5 2 
2
11
14
17 
21

样例输出 #1

4

数据范围与约定

对于 $100\%$ 的数据，保证 $1 \le L \le 10^9$，$0 \le M \le N \le 50000$。