Messenger in the Seven Kingdoms

Interview

Time limit2sMemory limit1024 MB

Summary

For each starting city, the messenger always moves to the nearest unvisited city, and the task asks for the smallest total squared distance over all starts.

Level: Easy3 of 10
Topics: Simulation, Brute force
Solved: No attempts yet

Statement

Once again the Seven Kingdoms have trouble. King Robert Baratheon has heard rumors of dragons, and he wants to warn all $n$ cities in the kingdom as soon as possible. Unfortunately, Joffrey, the king's son, shot almost all the carrier pigeons with a slingshot. Only one is left. The king wants to pick one city to send the messenger from, so that the messenger reaches all the other cities in the minimum time.

The messengers of the Seven Kingdoms are very lazy. They do not plan a route through the cities. They follow a fixed strategy instead:

Suppose the messenger is in city $i$ , and $M$ is the set of cities he has already visited. His next stop is city $j$ , the city closest to $i$ that is not in $M$ . If several cities are equally close, he goes to the one with the smallest number.

The cities are points on a plane with Cartesian coordinates $(x_i, y_i)$ . The time the messenger needs to travel between two cities is the squared Euclidean distance between their points.

Help King Robert choose the city from which the messenger visits all other cities in the minimum total time.

Input

The first line contains the number of cities $n$ ( $2 \le n \le 300$ ). Each of the next $n$ lines contains the coordinates $x_i$ and $y_i$ of one city ( $-300 \le x_i, y_i \le 300$ ).

Output

Print one line with the minimum time needed to notify all the cities.

Examples1

Example 1
Input
```
7
2 4
4 3
7 2
7 5
9 7
5 8
2 7
```
Expected output
```
51
```