In a remote area, there are N villages where mobile communication is absent. At one point, a major mobile provider allocated funds for the construction of one or two base stations in this area. Each station must be built directly in one of the villages. It only remains to determine in which villages to install the stations as well as choose their coverage radii so that residents of all the villages can use mobile phones.
It is clear that the larger the coverage radius of the station, the more expensive it is and the more electricity it consumes. Therefore, the provider decided to choose the locations for the stations and their coverage radii in such a way that the sum of the squares of the radii is minimal.
Determine in which villages to install the stations and what their coverage radii R1 and R2 should be, so that the sum R12 + R22 is minimized and every village is within the coverage area of at least one station. If one station is installed, the coverage radius of the second one can be considered equal to zero.
All villages are small, so they can be considered points. If a station serves a single village (where it is installed), then consider its coverage radius equal to 1.
The first line of input contains an integer N — the number of villages (2 ≤ N ≤ 500). The following N lines contain two integers in the range from 0 to 109 — the coordinates of the villages. It's guaranteed that no two pairs of coordinates coincide.
Output the minimum value of R12 + R22, rounded to the nearest integer.
4 0 1 1 0 4 1 5 3
7
3 0 0 1 0 2 0
1
3 0 0 5 0 0 1
2
In the first example, you can place the first station with a radius of 
in village 1 and the second station with a radius of 
in village 3.
In the second example, it is enough to take only one station with a radius of 1 and place it in village 2 — it will serve all three villages.
In the third example, you can place a station with a radius of 1 in village 1 and a second station with a radius of 1 in village 2.
