Problem Description

There is a very long straight road extending from west to east. There are $ N $ snowballs on the road.
The "position $ X $" on the road means a point that is $ X $ distance east from a reference point on the road.

The $ i $th snowball is located at position $ X_i $ from the west end of the road, with a radius of $ R_i $. Assume all snowballs are spherical.

E869120 wants to merge the snowballs to create the largest possible snowball.

Moving a snowball a distance $ d $ will reduce its radius by $ d $. When the radius becomes $ 0 $, the snowball disappears.
You can also merge snowballs at the same coordinates. Merging a snowball with radius $ r_1 $ and another with radius $ r_2 $ results in a snowball with radius $\left(r_1^3 + r_2^3\right)^{1/3}$.

What is the maximum radius of the snowball that E869120 can create?

Input Format

The input is given from the standard input in the following format:

$ N $ $ X_1 $ $ R_1 $ $ X_2 $ $ R_2 $ : : $ X_N $ $ R_N $

Output Format

Output the maximum radius of the snowball that E869120 can create in one line.
The answer will be considered correct if the relative or absolute error is within $ 10^{-4} $.

Sample Input and Output

Sample Input #1

2
4 5
7 9

Sample Output #1

9.03280211228081065

Sample Input #2

5
3 4
1 4
1 2
9 10
5 3

Sample Output #2

9.99999999999999645

Sample Input #3

9
815886884 307027576
432574413 156832535
869389414 537542354
8271358 844638329
34762585 93905560
445922147 508315922
476305579 724641385
15004200 341668840
277786703 825590503

Sample Output #3

1000677079.68994784

Notes/Hints

Constraints

• $1 \leq N \leq 100,000$
• $1 \leq X_i \leq 1,000,000,000$
• $1 \leq R_i \leq 1,000,000,000$

Subtasks and Points

This problem is divided into several subtasks. Your submission score will be the sum of the points for the subtasks you solve correctly.

1. (70 points): $ N = 2 $
2. (140 points): $N \leq 15$
3. (250 points): $N \leq 1,000$
4. (140 points): No additional constraints.

Sample Explanation 1

By performing the following operations, you can create a snowball with radius $ 737^{1/3} = 9.03280... $:
- Move the first snowball $ 3 $ distance east, reducing its radius by $ 3 $ to $ 2 $.
- Merge the first snowball with the second snowball. The resulting radius is $\left(9^3 + 2^3\right)^{1/3} = 9.03280...$. This is the maximum radius you can create.

Sample Explanation 2

The fourth snowball already has a radius of $ 10 $, and no larger snowball can be created in this case. Also, since an error up to $ 10^{-4} $ is allowed (see the "Output" section), outputs like 9.9992 or 10.000869120 are also acceptable.

Sample Explanation 3

Even though the radius and position constraints are up to $ 10^9 $, the answer can exceed $ 10^9 $.

见题面 Input 部分

见题面 Output 部分