题目描述

每年，奶牛都会举办一场以特殊版本的跳房子为特色的活动，包括小心地在河中从岩石跳到岩石。兴奋发生在一条又长又直的河流上，起点是一块岩石，终点是另一块岩石，距离 起点 $\red{L }$个单位$\red{（1 <= L <= 1,000,000,000）}$。

沿着河流的起点和终点之间的岩石，出现了 $\red{N (0 <= N <= 50,000) }$更多的岩石，每块岩石与起点的距离为 $\red{D_i (0 < D_i < L)}$。为了玩这个游戏，每头奶牛轮流 从起始岩石开始，并试图在结束岩石处到达终点，只从一块岩石跳到另一块岩石。当然，不太敏捷的奶牛永远不会到达最后一块岩石，而是最终落入河中。 $\red{Farmer John }$为他的奶牛感到自豪，并每年都会观看这一活动。

但随着时间的推移，他厌倦了看着其他农民胆怯的奶牛一瘸一拐地穿过放置得太近的岩石之间的短距离。他计划移除几块石头，以增加一头母牛必须跳到终点的最短距离。他知道 他无法移除开始和结束的石头，但他计算出他有足够的资源移除最多 $\red{M }$块石头 $\red{(0 <= M <= N)}$。

$\red{FJ }$想知道在开始移除岩石之前他可以将最短距离增加多少。帮助农夫约翰确定一头奶牛在移除最优的 $\red{M }$块岩石后必须跳跃的最 大可能最短距离。

数轴现在允许一块石头子的坐标为迪，现在要从$\red{0}$跳到$\red{L，}$每次条都从一个石子跳到第一个石子的下一个。$\red{FJ}$你$\red{M}$个石子问移动石头个子后，第二个石子尺寸的走样是多少。

输入格式

第 $\red{1 }$行：三个以空格分隔的整数：$\red{L}$、$\red{N }$和 $\red{M }$

第 $\red{2..N+1 }$行：每行包含一个整数，表示某块岩石与起始岩石的距离。没有两块石头在同一个位置。

输出格式

第 $\red{1 }$行：单个整数，表示牛在移除 $\red{M }$块石头后必须跳跃的最短距离的最大值

样例

输入样例

25 5 2
2
14
11
21
17

输出样例

4

提示

$\red{5}$块岩石，距离$\red{2}$、$\red{11}$、$\red{14}$、$\red{17}$和$\red{21}$。起始岩石位置$\red{0，}$在位置$\red{25}$处完成岩石。