O. Ya Masa2 El Geometry
time limit per test
5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Hussein, Kamal, Tawfik, and Gohary are setting up a new surveillance system in a large open field. They've marked $$$n$$$ important locations on the map, each represented as a point with coordinates $$$(x_i, y_i)$$$. Now, they must install at most two circular watchtowers so that every location is under surveillance — that is, every marked point lies inside or on the boundary of at least one of the circles.

A watchtower can be built anywhere on the map (not necessarily at one of the given locations) and can have any non-negative radius. A watchtower with radius $$$0$$$ can only cover a single point located exactly at its center.

The team wants to minimize the total coverage effort, defined as the sum of the radii of the two watchtowers used. If one watchtower is enough to cover all locations, the other one may have a radius of $$$0$$$.

Can you help them determine the minimum possible value of $$$r_1 + r_2$$$, where $$$r_1$$$ and $$$r_2$$$ are the radii of the two watchtowers?

Input

The first line contains an integer $$$n$$$ ($$$2 \le n \le 300$$$) — the number of marked locations.

Each of the next $$$n$$$ lines contains two integers $$$x_i, y_i$$$ ($$$-10^9 \le x_i, y_i \le 10^9$$$) — the coordinates of a location.

Output

Output a single real number — the minimum possible value of $$$r_1 + r_2$$$.

Your answer will be considered correct if its absolute or relative error does not exceed $$$10^{-6}$$$. Formally, let your answer be $$$a$$$ and the jury's answer be $$$b$$$. Your answer is considered correct if $$$\frac{|a - b|}{\max(1, |b|)} \le 10^{-6}$$$.

Examples
Input
10
907 -970
-743 -745
-860 -454
-346 -318
162 366
-650 671
-110 -830
914 864
609 -443
175 -52
Output
1131.0537122524
Input
3
-865 -635
-680 -783
-360 510
Output
118.4577983925