Little Joseph went kayaking in Pulau Ubin and he must visit a few nature spots. However, because of the high tide and the low tide, Little Joseph can only move right in the morning and left in the afternoon. He must start and end at his campsite (the campsite will always be the leftmost point). This means that Little Joseph has to start from the leftmost point and only move right all the way onto the rightmost point, and then return by only moving left all the way back to the leftmost point.
Given the coordinates of all the nature spots/campsite, what is the shortest distance the kayak must travel to complete the whole route? Note that the x coordinate of each point is unique.
Input
The first line contains an integer n, representing the number of points Little Joseph must visit (including the campsite)
The next
n lines contain two integers representing the
x and
y coordinates of the point respectively.
Output
Print out the shortset distance the kayak must travel (print out to the
NEAREST integer. If the answer is 2.7, you should print out 3)
Sample Input 1
7
0 0
1 6
2 3
5 2
6 5
7 1
8 4
Sample Output 1
26
[Explanation: The shortest route is moving from (0,0) to (2,3) to (5,2) to (7,1) to (8,4) to (6,5) to (1,6) and finally back to (0,0) giving a length of about 25.58, hence the answer is 26]
Limits
For 30% of the test cases,
n<10
For 60% of the test cases,
n<100
For 100% of the test cases,
n<1000