Minimum Distance for Cheese Hunt

A mouse starts at the point (0,0) and there are n pieces of cheese located in a room. The mouse wants to eat all the cheeses. Your task is to determine the minimum total distance the mouse must travel in order to eat all the cheeses. Note that the mouse does not have to return to the starting point after eating the last piece.

The distance between two points \((x_1, y_1)\) and \((x_2, y_2)\) is defined as \[ d=\sqrt{(x_2-x_1)^2+(y_2-y_1)^2} \]

Note: Since the problem is NP-hard in general, you can assume that n is small (for example, \(n \le 10\)).

inputFormat

The first line contains an integer n (\(1 \le n \le 10\)), the number of cheese pieces.

Each of the next n lines contains two space-separated integers representing the x and y coordinates of a piece of cheese.

outputFormat

Output a single line containing the minimum distance the mouse must travel. The answer should be printed with precision up to 6 decimal places.

sample

1
3 4

5.000000