For given $N$ points in the 2D Euclidean plane, find the distance of the shortest tour that meets the following criteria:

* Visit the points according to the following steps:
1. It starts from the leftmost point (starting point), goes strictly from left to right, and then visits the rightmost point (turn-around point).
2. Then it starts from the turn-around point, goes strictly from right to left, and then back to the starting point.
* Through the processes 1. 2., the tour must visit each point at least once.

Constraints

* $2 \leq N \leq 1000$
* $-1000 \leq x_i, y_i \leq 1000$
* $x_i$ differ from each other
* The given points are already sorted by x-coordinates

Input

The input data is given in the following format:

$N$
$x_1$ $y_1$
$x_2$ $y_2$
...
$x_N$ $y_N$

Output

Print the distance of the shortest tour in a line. The output should not have an error greater than 0.0001.

Examples

Input

3
0 0
1 1
2 0


Output

4.82842712


Input

4
0 1
1 2
2 0
3 1


Output

7.30056308


Input

5
0 0
1 2
2 1
3 2
4 0


Output

10.94427191

Source: aizu | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
import math
pts = []
line = input()
N = int(line)
for _ in range(0, N):
	line = input()
	(x, y) = list(map(int, line.split()))
	pts += [[x, y]]

def dist(i, j):
	(x1, y1) = pts[i]
	(x2, y2) = pts[j]
	return math.sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2)

def btsp():
	dp = [[0] * N for _ in range(0, N)]
	for i in range(1, N):
		dp[0][i] = dp[0][i - 1] + dist(i - 1, i)
	for i in range(1, N):
		for j in range(i, N):
			if i == j - 1 or i == j:
				m = 10 ** 10
				for k in range(0, i):
					m = min(m, dp[k][i] + dist(j, k))
				dp[i][j] = m
			else:
				dp[i][j] = dp[i][j - 1] + dist(j - 1, j)
	return dp[N - 1][N - 1]
print(btsp())


import sys
from math import sqrt
readline = sys.stdin.readline
write = sys.stdout.write
N = int(readline())
PS = [list(map(int, readline().split())) for i in range(N)]
PS.sort()

def dist(P, Q):
	return sqrt((P[0] - Q[0]) ** 2 + (P[1] - Q[1]) ** 2)
INF = 10 ** 18
S = [INF] * N
T = [INF] * N
S[0] = T[0] = dist(PS[0], PS[1])
for k in range(2, N):
	s = t = INF
	for i in range(k - 1):
		d = dist(PS[i], PS[k])
		s = min(s, T[i] + d)
		t = min(t, S[i] + d)
	S[k - 1] = s
	T[k - 1] = t
	d = dist(PS[k - 1], PS[k])
	for i in range(k - 1):
		S[i] += d
		T[i] += d
print(min((min(s, t) + dist(PS[i], PS[N - 1]) for (i, (s, t)) in enumerate(zip(S, T)))))


import sys
import math
import collections
import bisect
import itertools
import fractions
import copy
import decimal
import queue
sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7
ni = lambda : int(sys.stdin.readline())
ns = lambda : map(int, sys.stdin.readline().split())
na = lambda : list(map(int, sys.stdin.readline().split()))
eps = 10 ** (-9)

def main():
	n = ni()
	e = []
	for _ in range(n):
		(xi, yi) = ns()
		e.append([xi, yi])
	dp = [[INF for _ in range(n)] for _ in range(n)]
	dist = lambda p1, p2: math.sqrt((p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2)
	dp[0][0] = 0
	for i in range(n - 1):
		for j in range(n):
			if dp[i][j] != INF:
				dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + dist(e[i], e[i + 1]))
				dp[i + 1][i] = min(dp[i + 1][i], dp[i][j] + dist(e[j], e[i + 1]))
	for i in range(n):
		dp[n - 1][n - 1] = min(dp[n - 1][n - 1], dp[n - 1][i] + dist(e[n - 1], e[i]))
	print(dp[n - 1][n - 1])
main()


import math
from typing import List, Tuple

def dist(p1: Tuple[int, int], p2: Tuple[int, int]) -> float:
	return math.sqrt((p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2)
N = int(input())
points: List[Tuple[int, int]] = [(0, 0)] * N
for idx in range(N):
	(x, y) = map(lambda x: int(x), input().split())
	points[idx] = (x, y)
table1 = [float('inf')] * N
table2 = [float('inf')] * N
table1[0] = table2[0] = dist(points[0], points[1])
for i in range(2, N):
	d1 = d2 = float('inf')
	for j in range(i - 1):
		d = dist(points[i], points[j])
		d1 = min(d1, table2[j] + d)
		d2 = min(d2, table1[j] + d)
	table1[i - 1] = d1
	table2[i - 1] = d2
	d = dist(points[i - 1], points[i])
	for j in range(i - 1):
		table1[j] += d
		table2[j] += d
ans = min((min(d1, d2) + dist(points[i], points[N - 1]) for (i, (d1, d2)) in enumerate(zip(table1, table2))))
print(ans)


import sys
sys.setrecursionlimit(1000000)

def calc(p1, p2, v):
	dists_v = dists[v]
	if v == n - 1:
		return dists_v[p1] + dists_v[p2]
	if visited[p1][p2]:
		return dp[p1][p2]
	dp[p1][p2] = min(dists_v[p1] + calc(p2, v, v + 1), dists_v[p2] + calc(p1, v, v + 1))
	visited[p1][p2] = True
	return dp[p1][p2]
n = int(input())
points = [complex(*map(int, input().split())) for _ in range(n)]
dists = [[abs(p1 - p2) for p2 in points] for p1 in points]
visited = [[False] * n for _ in range(n)]
dp = [[0] * n for _ in range(n)]
print(calc(0, 0, 0))


import sys
from math import sqrt
sys.setrecursionlimit(1000000)
iim = lambda : map(int, input().rstrip().split())

def resolve():
	N = int(input())
	P = [list(iim()) for i in range(N)]

	def dist(i, j):
		x = P[i][0] - P[j][0]
		y = P[i][1] - P[j][1]
		return sqrt(x * x + y * y)

	def tsp(i, j, k):
		if i == 0 and j == 0:
			return dist(0, 1) + tsp(0, 1, 0)
		else:
			if dp[i][j]:
				return dp[i][j]
			if k == N:
				return dist(i, j)
			d1 = dist(i, k) + tsp(k, j, k + 1)
			d2 = dist(j, k) + tsp(i, k, k + 1)
			d = d1 if d1 < d2 else d2
			dp[i][j] = d
			return d
	dp = [[0] * N for i in range(N)]
	print(tsp(0, 0, 0))
resolve()