Problem Description

There are $ N $ points on a number line, where the coordinate of the $ i $ -th point is $ x_i $. Additionally, $ N $ integers $ w_i $ are given.

Find the coordinate of the point $ p $ that satisfies the following condition. If there are multiple points that satisfy the condition, find the one with the smallest coordinate.

Condition: "The maximum value of ($ p $ to point $ i $ distance) × $ w_i $ for integers $ i $ satisfying $1\ \leq\ i\ \leq\ N$ is minimized."

Input Format

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

$ N $ $ x_1 $ $ w_1 $ : $ x_N $ $ w_N $

Output Format

Output the smallest coordinate of the point $ p $ that satisfies the condition. The answer will be considered correct if the absolute or relative error is at most $ 10^{-9} $.

Sample Input and Output

Sample Input #1

6
-9 1
-6 1
-4 1
1 1
9 1
10 1

Sample Output #1

0.500000000000

Sample Input #2

20
-8965725 4915988
-8830129 1578539
-8356752 3503810
-7479989 5100308
-6995994 3722838
-6861764 3493854
-6486775 1657800
-4577872 7994227
-3685008 7178154
-3169623 9319261
-2694681 7493276
-1967934 3837689
-1634671 544297
-1232484 6010778
2733239 4318924
4797695 2789412
5713704 4416095
6609027 2426329
6997023 2155233
7812383 9912027

Sample Output #2

2249873.278320866637

Notes/Hints

Constraints

• $1\ \leq\ N\ \leq\ 10^5$
• $|x_i|\ \leq\ 10^7$
• $x_i\ <\ x_{i+1}$ ($1\ \leq\ i\ \leq\ N-1$)
• $1\ \leq\ w_i\ \leq\ 10^7$
• All values given in the input are integers

Sample Explanation 1

When the coordinate of point $ p $ is $ 0.5 $, the values of ($ p $ to point $ i $ distance) × $ w_i $ for each point $ i $ ($1\ \leq\ i\ \leq\ N$) are $9.5,\ 6.5,\ 4.5,\ 0.5,\ 8.5,\ 9.5$ respectively, and the maximum value among these is $ 9.5 $. This value cannot be made smaller, so the answer is $ 0.5 $.

见题面 Input 部分

见题面 Output 部分