AT_s8pc_6_d Snowballs

[problemUrl]: https://atcoder.jp/contests/s8pc-6/tasks/s8pc_6_d 西から東に延びる十分に長い一直線の道路があります。道路には $ N $ 個の雪玉があります。 道路上で「$ X $ の位置」とは、ある道路上の地点を基準として距離 $ X $ だけ東に進んだ位置という意味です。 $ i $ 個目の雪玉は、道路の西端から $ X_i $ の位置にあり、半径は $ R_i $ です。すべての雪玉は球体であると仮定してもよいです。 E869120 君は、雪玉を合体させてできるだけ大きい雪玉を作ろうと考えました。 雪玉を距離 $ d $ 動かすと、半径は $ d $ 小さくなります。半径が $ 0 $ になると、雪玉は消滅します。 また、同じ座標にある雪玉を合体させることもできます。半径 $ r_1 $ の雪玉と半径 $ r_2 $ の雪玉を合体させると、半径 $ \left(r_1^3\ +\ r_2^3\right)^{1/3} $ の雪玉になる。 さて、E869120 君が作れる最大の雪玉の半径はいくつでしょうか？

入力は以下の形式で標準入力から与えられます。 > $ N $ $ X_1 $ $ R_1 $ $ X_2 $ $ R_2 $ : : $ X_N $ $ R_N $

E869120 君が作れる最大の雪玉の半径を $ 1 $ 行で出力してください。 ただし、相対誤差または絶対誤差が $ 10^{-4} $ 以内の場合、正答とみなされる。

### 制約 - $ 1\ \leq\ N\ \leq\ 100\ 000 $ - $ 1\ \leq\ X_i\ \leq\ 1\ 000\ 000\ 000 $ - $ 1\ \leq\ R_i\ \leq\ 1\ 000\ 000\ 000 $ ### 小課題・得点 この問題はいくつかの小課題に分けられ、その小課題のすべてのテストケースに正解した場合に「この小課題に正解した」とみなされます。 提出したソースコードの得点は、正解した小課題の点数の合計となります。 1. (70 点)：$ N\ =\ 2 $ 2. (140 点)：$ N\ \leq\ 15 $ 3. (250 点)：$ N\ \leq\ 1\ 000 $ 4. (140 点)：追加の制約はない。 ### Sample Explanation 1 次のような操作をすると、半径 $ 737^{1/3}\ =\ 9.03280... $ の雪玉を作ることができます。 - $ 1 $ 個目の雪玉を、距離 $ 3 $ だけ東に移動させます。すると、半径が $ 3 $ 減って $ 2 $ になります。 - $ 1 $ 個目の雪玉と $ 2 $ 個目の雪玉を合体させます。合体後の半径は $ \left(9^3\ +\ 2^3\right)^{1/3}\ =\ 9.03280... $ になります。 これが作れる最大の雪玉の半径になります。 ### Sample Explanation 2 $ 4 $ 個目の雪玉は最初から半径 $ 10 $ ですが、このケースではこれ以上の大きさの雪玉をどうやっても作ることができません。 また、誤差が $ 10^{-4} $ まで認められるので (「出力」セクション参照)、例えば `9.9992` や `10.000869120` などの出力をしてもよいです。 ### Sample Explanation 3 半径・位置の制約が $ 10^9 $ 以下であるとはいえ、答えが $ 10^9 $ を超える場合があります。