問題文

左右の長さが L [cm] のようかんがあります。 N 個の切れ目が付けられており、左から i 番目の切れ目は左から A_i [cm] の位置にあります。

あなたは N 個の切れ目のうち K 個を選び、ようかんを K+1 個のピースに分割したいです。そこで、以下の値を スコア とします。

• K+1 個のピースのうち、最も短いものの長さ（cm 単位）

スコアが最大となるように分割する場合に得られるスコアを求めてください。

制約

• 1 \leq K \leq N \leq 100000
• 0 \lt A_1 \lt A_2 \lt \cdots \lt A_N \lt L \leq 10^9
• 入力はすべて整数

入力例 1

3 34
1
8 13 26

出力例 1

13

左から 2 番目の切れ目で分割すると、長さ 13 [cm] のピースと長さ 21 [cm] のピースに分かれ、スコア 13 を達成できます。

入力例 2

7 45
2
7 11 16 20 28 34 38

出力例 2

12

左から 3 番目と 5 番目の切れ目で分割すると、スコア 12 を達成できます。

入力例 3

3 100
1
28 54 81

出力例 3

46

左から 2 番目の切れ目で分割すると、スコア 46 を達成できます。

入力例 4

3 100
2
28 54 81

出力例 4

26

入力例 5

20 1000
4
51 69 102 127 233 295 350 388 417 466 469 523 553 587 720 739 801 855 926 954

出力例 5

170