根树是一种有向无环图,包含一个节点(根),从该节点到任何其他节点只有一条路径。
如果每个节点最多有两个传出弧,则根树是二叉树。
当在平面上绘制二叉树时,所有弧都应从上到下。也就是说,从 u 到 v 的每条弧必须满足条件 yu > yv。
您已获得所有树节点的坐标。你的任务就是用弧连接这些节点,得到二叉根树,并使弧的总长度最小。所构建树的所有弧线必须从上到下。
输入
第一行包含一个整数 n (2 ≤ n ≤ 400) — 树中的节点数。然后跟随 n 行,每行两个整数: xi, yi (|xi|, |yi| ≤ 103) — 节点的坐标。保证所有点都是不同的。
输出
如果无法在给定点上构建二叉根树,则打印“-1”。否则,打印一个实数——最小二叉树中弧的总长度。如果绝对误差或相对误差不超过 10 - 6,则答案将被视为正确。
示例
输入 #1
3 0 0 1 0 2 1
输出 #1
3.650281539872885
输入 #2
4 0 0 1 0 2 1 2 0
输出 #2
-1