你可能知道，17 世纪时，一群荷兰人在曼哈顿岛上建立了一个名为新阿姆斯特丹（New Amsterdam）的定居点，后来发展成了纽约市。鲜为人知的是，另一群荷兰人也移居美国，并建立了一个名为新代尔夫特（New Delft）的城市。和它的“大兄弟”一样，新代尔夫特也是建立在一个由两组平行街道组成的网格上，这两组街道相互垂直。

新代尔夫特已经建成了一些糖浆华夫饼（stroopwafel）面包店，但还没有修建任何街道。你的任务是规划街道网格。为此，你需要确定网格的方向，使得两类街道有两个正交的方向。一旦确定了方向，你就可以修建任意街道，只要每条街道都符合给定的两个方向之一，如图 J.1 所示。每条街道都可以双向通行。

图 J.1：样例输入 2 的示意图，展示了一种可能的街道布局，该布局提供了访问所有面包店的最短路径。

街道布局应以最优方式创建，以供一年一度的“糖浆华夫饼跑”（Stroopwafel Run）使用。这是一项活动，参赛者需要以他们选择的某种顺序访问所有面包店，并且他们可以在城市中的任何一点开始和结束跑步。你的任务是设计一种网格布局，使得这条最短路径尽可能短。

输入格式

输入包含： 一行包含一个整数 $n$ ($2 \le n \le 12$)，表示新代尔夫特的面包店数量。 $n$ 行，每行包含两个整数 $x$ 和 $y$ ($0 \le x, y \le 10^6$)，表示其中一家面包店的坐标。

面包店位于不同的坐标处，因此对于任何 $1 \le i, j \le n$ 且 $i \neq j$，都有 $(x_i, y_i) \neq (x_j, y_j)$。

输出格式

输出在最优网格布局下，访问所有面包店的最短路径长度。

你的答案的绝对误差或相对误差应不超过 $10^{-6}$。

样例

样例输入 1

3
0 1
1 2
3 0

样例输出 1

4.24264068712

样例输入 2

4
1 4
6 0
5 3
2 6

样例输出 2

11.1566387517