弦线艺术

时间限制：1 秒
内存限制：256 MB
输入：标准输入
输出：标准输出

题目描述

在日本，最近流行一种弦线艺术（стринг-арт）：通过在钉入木板的钉子之间缠绕细线来创作图像。

一位初学日本艺术家在编号为 $1$ 到 $n$ 的 $n$ 个钉子上作抽象画，钉子按照在木板上从左到右的顺序编号。每个钉子的坐标已知：第 $i$ 个钉子位于 $(x_i, y_i)$，且满足 $x_1 \le x_2 \le \ldots \le x_n$。

作为图像的基础，艺术家想只用两根细线来创建基本图形，目前两根细线都系在第一个钉子上。为了使基本图像足够完整和谐，艺术家希望满足以下要求：

• 如果某根细线最后一次系在编号为 $i$ 的钉子上，那么它下一次只能系在编号大于 $i$ 的钉子上。换句话说，每根细线上的结点编号必须严格递增。
• 每个钉子至少使用一次，即对任意 $i$，要么第一根细线在 $i$ 号钉子上有结点，要么第二根细线有结点，或者两者都有。
• 两根细线的总长度应尽可能小。

钉子 $i$ 和 $j$ 之间的距离为 $\sqrt{(x_i - x_j)^2 + (y_i - y_j)^2}$。所用细线的总长度等于其相邻结点之间的距离之和。每根细线可以系在任意多个钉子上，且两根细线的最后一个钉子不必相同。

确定满足所有条件的弦线艺术图像的最佳基础，即最小化细线总长度。

输入格式

第一行包含一个整数 $n$ ——木板上的钉子数 ($2 \le n \le 2000$)。

接下来的 $n$ 行，第 $i$ 行给出两个整数 $x_i$ 和 $y_i$ ——第 $i$ 个钉子的坐标 ($|x_i|, |y_i| \le 10^9$)。保证 $x_1 \le x_2 \le \ldots \le x_n$。

输出格式

输出一个数 —— 所需的最小细线总长度。如果绝对或相对误差不超过 $10^{-6}$，答案被视为正确。

评分系统

子任务分数仅当该子任务及其所需子任务的所有测试均通过时才给予。

样例

样例 1

输入

2
0 0
3 4

输出

5.0000000000

样例 2

输入

3
0 0
1 10
2 0

输出

12.0498756211

样例 3

输入

4
0 0
2 0
5 0
9 0

输出

9.0000000000

样例 4

输入

5
0 0
1 4
2 1
3 5
4 0

输出

10.8313095581