C0750 坐标选点
坐标选点
题目描述
修建了一条长度为 m 公里的铁路，起点和终点已经建有火车站。铁路沿线有 n 座城市(城市不位于起点或终点)，第 i 座城市到铁路起点的距离为 ai 公里。
现在计划在这 n 座城市中选择 c 座修建火车站，使得所有火车站(包括起点和终点的火车站)之间的最小相邻距离尽可能大。请你计算这个最小相邻距离的最大可能值。
输入
第一行包含三个正整数n、c、m，分别表示城市数量、计划修建的火车站数量以及铁路总长度。
第二行包含n个正整数a1,a2,...,an，表示每座城市到铁路起点的距离。
输出
输出一个整数，表示最小相邻距离的最大可能值。
数据范围
1≤c≤n≤10^6，1≤ai<m≤10^9，输入中的所有数值均为整数
输入样例1
5 3 10
1 2 8 4 9
输出样例1
2