Our favorite guide realized that in the first part, a prank was pulled that ruined his chances of winning. Defeated, embarrassed, and dusty, the guide has hatched a plan for revenge. This time, the home-field advantage is on his side, and Mr. Malnar seemingly has no chance. Namely, it is a race! This is not a 100-meter dash or some measly marathon; this is an epic race between two cities in the land of fire. The only rule is that there are no rules, and all that matters is arriving from the starting city to the destination city before the opponent.

The guide decided to race by bicycle because he knows that all intercity roads for cars are currently closed. Since he knows that Mr. Malnar is unaware of this fact and considers himself physically superior, he will allow him to choose which cities to race between.

However, the guide does not know that Mr. Malnar has already rented a private helicopter in case he needs to do some things on the other side of the city. Naturally, Mr. Malnar accepted the challenge, but he also felt a little sorry for the poor guide, so he decided to choose a route where he would win with the smallest possible margin.

Cities in Azerbaijan can be represented as points in a coordinate system. Intercity bicycle paths take the form of a rectangular grid, so the guide can only move parallel to the coordinate axes. On the other hand, Mr. Malnar will move between cities along the line segment connecting them. More precisely, if the starting city is at point $(x_1, y_1)$ and the destination is at point $(x_2, y_2)$, the guide will cover a distance $d_v = |x_1 - x_2| + |y_1 - y_2|$, while Mr. Malnar will cover a distance $d_m = \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}$.

Mr. Malnar will choose a pair of cities for which the ratio $\frac{d_v}{d_m}$ is the smallest possible. Determine that ratio!

Input

The first line contains a natural number $n$ ($2 \le n \le 300\,000$).

The $i$-th of the next $n$ lines contains integers $x_i, y_i$ ($0 \le |x_i|, |y_i| \le 10^9$) representing the coordinates of the $i$-th city. No two cities will be at the same coordinates.

Output

The first line must contain the requested ratio.

An absolute or relative error of $10^{-10}$ will be tolerated.

Examples

Input 1

5
1 2
3 7
4 4
5 6
8 8

Output 1

1.176696810829104

Input 2

6
5 5
2 7
-3 8
-5 -5
-10 1
6 -4

Output 2

1.086428952510222