Description

平面上有n个点P1,P2,...,Pn,你的任务是把它们配成n/2对(n是偶数)，使得每个点恰好在一个点对中。所有点对中两点的距离之和应尽量小。n<=20,|xi|,|yi|<=10000。

Input

第一行输入n(2到20之间的偶数)
接下来n行，每行输入两个整数表示xi,yi。|xi|,|yi|<=10000。

Output

输出最小配对距离。答案保留两位小数

Sample 1

Input

4
8730 9323
-3374 3929
-7890 -6727
1257 4689

Output

20366.60

Limitation

时间限制1s, 空间限制262144KiB

Sign

这题是状压DP，每次处理一对点，求当前阶段最小距离