Safe Bridge

問題文

谷に長さ $L$ の一直線の橋をかけます。柱の設置位置の候補は $N$ 個あり、橋の左端から距離$X_i$に柱を建設する場合のコストは $Y_i$ です。隣り合う柱や橋の端の間隔の最大値を「橋の危険度」と呼びます。より正確には、建設する柱の位置を昇順に$y_1, y_2, \cdots y_k$とし、$y_0=0$, $y_{k+1}=L$としたとき、橋の危険度は$\underset{0 \leq i \leq k}{\mathrm{Max}}(y_{i+1}-y_i)$ であり、特に柱が0本の場合、 $L$ です。コスト $C$ 以内で柱を0本以上建設するとき、橋の危険度の最小値を求めてください。

制約

• $1 \leq N \leq 2\times 10^5$
• $1 \leq L, C \leq 10^9$
• $0 < X_1 < X_2 < \cdots < X_N < L$
• $1 \leq Y_i \leq 10^9 (1 \leq i \leq N)$
• 入力される値はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

出力

答えを1行で出力せよ。

サンプル 1

入力

4 10 90
3 5 6 8
20 40 10 30

出力

3

サンプル 2

入力

20 100 200
11 16 21 23 26 31 33 37 38 47 49 55 63 65 72 75 91 94 95 96
3 19 24 29 37 48 51 52 59 60 62 62 67 72 73 74 80 85 90 98

出力

25

サンプル 3

入力

5 20 10
3 5 11 17 19
34 23 64 28 59

出力

20