B - カードゲーム Editorial /

Time Limit: 5 sec / Memory Limit: 256 MB

問題文

すぬけ君はすめけさんと二人で数の書かれたカードとコインを使って以下のようなゲームをすることにしました。

はじめ、すぬけ君は T が書かれたカード一枚と K 枚のコインを、すめけさんはカードを N 枚持っている。
このゲームは N 回のラウンドに分かれていて、すめけさんは各ラウンドでは以下の手順を一回行う。

  • すめけさんはまだすぬけ君に見せていないカードを一枚選び、それをすぬけ君に見せる。このカードに書かれている数字を A とする。
  • すぬけ君の持っているカードに書かれた数字を B とすると、すぬけ君はすめけさんから|A-B| ダメージを受ける。
  • すぬけ君はコインを持っているとき、すめけさんにコインを一枚渡して A のカードを B のカードと交換するか、コインを渡さずに何もしないかのどちらかを行う。
このゲームにおいて、すぬけ君は各ラウンドで受けるダメージの最大値を最小化したい。

そこで、すぬけ君はすめけさんの作戦を探り出し、すめけさんはすぬけ君の行動に関わらず i 回目に書かれている値が A_i のカードを出すのだと確信した。

すぬけ君が各ラウンドで受けるダメージの最大値として考えられる最小の値を求めてくさだい。
ただし、各ラウンドが終わった後、すぬけ君のダメージはすめけさんによって回復されることとする。

入力

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

N T K
A_1 A_2 ... A_N
  • 一行目にはラウンドの数 N(1≦N≦100,000)とすぬけ君が最初に持っているカードに書かれている数 T(1≦T≦10^{9})、コインの枚数 K(1≦K≦N) が与えられる。
  • 次の行にはN 個の数が与えられ、i 個目の整数としてすめけさんが i(1≦i≦N) 回目に出すカードに書かれている数 A_{i}(1≦A_{i}≦10^{9}) が与えられる。

配点

この問題には部分点があります。追加制約として、 N=K を満たす場合についてこの問題を解くと20点が与えられます。

出力

すぬけ君が各ラウンドで受けるダメージの最大値として考えられる最小の値を一行に出力せよ。 末尾には改行を入れること。

入力例1

5 1 1
1 2 3 4 5

出力例1

2

入力例2

8 9 3
11 4 5 14 19 19 8 10

出力例2

6