You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

奶牛们每年都会举办一次活动，内容是一种奇特的跳房子游戏，即在河中小心翼翼地从一块石头跳到另一块石头。 比赛在一条笔直的长河上进行，起点有一块石头，终点有另一块石头，距离起点 $L$ 个单位（$1 \le L\le 1,000,000,000$）。 在起点和终点岩石之间的河道上，会出现 $N$ 个（$0\le N\le 50,000$ 个）更多的岩石，每个岩石与起点的距离为一个整数 $D_i$（$0<D_i<L$）。

玩游戏时，每头牛依次从起点岩石开始，努力到达终点岩石，只能从一个岩石跳到另一个岩石。 当然，不那么灵活的奶牛永远也到不了终点岩石，最后只能掉进河里。

农场主约翰为自己的奶牛感到骄傲，每年都会观看这项比赛。 但随着时间的推移，他已经厌倦了看着其他农户的胆小的奶牛一瘸一拐地走过石头之间的短距离。 他计划移走几块石头，以增加奶牛跳到终点的最短距离。 他知道自己无法移走起点和终点的石头，但他计算出自己有足够的资源移走最多 $M$ 块石头（$0 \le M \le N$）。

FJ 想知道，在开始移走石头之前，他能将最短距离增加多少。 请帮助农场主约翰确定在移走最优的 $M$ 组石块后，奶牛要跳过的最短距离。

形式化中文题意：

对于给定在一维位置的 $N$ 个点，选择 $M$ 个点进行移除，使得每两个点之间的距离最小值最大。

输入格式

第 $1$ 行，三个空格分隔的整数：$L$、$N$ 和 $M$。

第 $2\dots N+1$ 行，每行包含一个整数，表示某块岩石距离起始岩石的距离。 没有两块石头的位置相同。

输出格式

一个整数，即奶牛在移走 $M$ 块石头后所需跳跃的最短距离的最大值。

25 5 2
2
14
11
21
17

4

提示

在移除任何石块之前，最短的跳跃是从 $0$（起点）到 $2$ 的 $2$ 级跳；在移除 $2$ 和 $14$ 处的石块之后，所需的最短跳跃是 $4$ 级跳（从 $17$ 到 $21$ 或从 $21$ 到 $25$）。