Minimizing the Maximum Monster Strength

Teacher Qiu is a fantasy monster enthusiast. He owns n monsters; each monster has two attributes: attack power \(\mathrm{atk}\) and defense power \(\mathrm{dnf}\). Determined to become a monster master, he embarks on a journey leaving Zhenxin Town to explore the unknown.

The environment has a great influence on the monsters’ combat effectiveness. An environment is defined by two positive real parameters \(a\) and \(b\). In environment \((a,b)\), each monster may either decrease its attack by an amount \(k\times a\) to increase its defense by \(k\times b\), or increase its attack by \(k\times a\) while decreasing its defense by \(k\times b\). Here \(k\) can be any real number, with the constraint that the final attack and defense values remain nonnegative at all times.

The combat strength of a monster in environment \((a,b)\) is defined as the sum of the maximum achievable attack power and the maximum achievable defense power. In other words, if a monster has initial attack \(x\) and defense \(y\), then by choosing the optimal adjustment (and an appropriate real number \(k\)) under the constraints, its maximum possible attack and defense values are:

• Maximum attack: \(x + \frac{y}{b} \times a\) (by increasing attack) , since if we choose \(k=\frac{y}{b}\), then the defense becomes \(y - \frac{y}{b}\times b = 0\).
• Maximum defense: \(y + \frac{x}{a}\times b\) (by increasing defense) , since if we choose \(k=\frac{x}{a}\), then the attack becomes \(x - \frac{x}{a}\times a = 0\).

Thus, the combat strength of this monster in environment \((a,b)\) is \[ \mathrm{strength}(a,b)=x+y+\frac{x}{r}+r\,y, \quad \text{where } r=\frac{a}{b}>0. \]

Since different environments \((a,b)\) may favor different monsters, Teacher Qiu seeks to determine the worst‐case scenario for his collection. In other words, he wants to know the minimum possible value of the best combat strength among his n monsters, when the environment is chosen adversarially. Formally, if for each monster \(i\) with attributes \(\mathrm{atk}_i = x_i\) and \(\mathrm{dnf}_i = y_i\) the strength is \[ S_i(r)=x_i+y_i+\frac{x_i}{r}+r\,y_i, \quad r>0, \] then define \[ F(r)=\max_{1\le i\le n} S_i(r). \] Teacher Qiu wants to find \[ \min_{r>0} F(r). \]

It can be shown that \(F(r)\) is a convex function of \(r\) (since it is the maximum of convex functions), so the minimum value can be found by optimization techniques such as ternary search.

Given the attributes of the n monsters, output the minimum possible maximum combat strength that can be achieved by choosing an appropriate environment \((a, b)\), with an absolute or relative error of at most \(10^{-6}\).

inputFormat

The first line contains a single integer \(n\) (\(1 \le n \le 10^5\)), the number of monsters. Each of the next \(n\) lines contains two nonnegative numbers \(x\) and \(y\) (\(0 \le x,y \le 10^9\)), representing the attack and defense of a monster respectively.

Note: The values \(x\) and \(y\) may be integers or real numbers.

outputFormat

Output a single real number, which is the minimized maximum combat strength among the monsters. Your answer is accepted if its absolute or relative error does not exceed \(10^{-6}\).

sample

1
6 2

14.92820323