#2455. 跳房子游戏

跳房子游戏

Description

跳房子游戏指从河中的一块石头跳到另一块石头,这发生在一条又长又直的河流中,从一块石头开始,到另一块石头结束。长度为L1L109L (1≤L ≤10^9 ),从开始到结束之间的石头数量为N0N50000N (0≤N ≤50 000),从每块石头到开始位置有一个整数距离di0<di<Ldi(0<di <L )。 为了玩游戏,每头母牛都依次从起始石头开始,并尝试到达终点的石头,只能从石头跳到石头。 当然,不那么灵活的母牛永远不会到达最后的石头,而是掉进河中。 约翰计划移除几块石头,以增加母牛必须跳到最后的最短距离。不能删除起点和终点的石头,但约翰有足够的资源移除多达MM 块石头0MN(0≤M ≤N )。请确定在移除MM 块石头后,母牛必须跳跃的最短距离的最大值。

Input

第1行包含3个整数LNL 、NMM 。接下来的NN 行,每行都包含一个整数,表示从该石头到起始石头的距离。没有两块石头有相同的位置。

Output

单行输出移除MM 块石头后母牛必须跳跃的最短距离的最大值。

Samples

25 5 2
2
14
11
21
17
4

来源

POJ3258