AT_ijpc2015_e カードゲーム

[problemUrl]: https://atcoder.jp/contests/ijpc2015-2/tasks/ijpc2015_e すぬけ君はすめけさんと二人で数の書かれたカードとコインを使って以下のようなゲームをすることにしました。 はじめ、すぬけ君は $ 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点が与えられます。