题目描述

越野跑是一项在露天自然地形上进行的赛跑运动。为了记录参赛者的比赛进度，组织者设置了若干 RFID 检查点；每个检查点覆盖平面上的一条线段。

当一名参赛者依次穿过编号为 $1,2,\ldots,n$ 的全部检查点后，就完成了比赛。

如果参赛者在错误的顺序下穿过某个检查点，不会获得任何好处，也不会受到处罚；他只需要在之后轮到该检查点时再次穿过它即可。因此，为了更快到达终点，参赛者可以先穿过某个检查点，随后立刻沿另一个方向再次穿过它。

样例 3 的最优路线

上图展示了样例输入 3 的一条最优路线。

请计算完成比赛所需跑过的最短距离，以便将其作为这条赛道的官方长度。

输入格式

第一行包含一个整数 $n$，表示检查点数量。

第二行包含两个整数 $x_s,y_s$，表示比赛起点的坐标。

接下来 $n$ 行，第 $i$ 行包含四个整数

表示第 $i$ 个检查点线段的两个端点。

最后一行包含两个整数 $x_t,y_t$，表示比赛终点的坐标。

输出格式

输出一个实数，表示从起点出发，按照 $1,2,\ldots,n$ 的顺序穿过全部检查点并最终到达终点所需的最短距离。

途中可以多次穿过某些检查点，也可以在尚未轮到某个检查点时提前穿过它。

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

数据范围

• $1\le n\le 16$；
• $-10^6\le x_s,y_s,x_t,y_t\le 10^6$；
• 所有检查点端点的坐标均在 $[-10^6,10^6]$ 内；
• 每个检查点的长度均非零；
• 不同检查点之间可以重叠；
• 检查点也可以与起点或终点重叠。

样例 1

输入

2
0 1
10 0 10 2
20 2 20 0
30 1

输出

30

样例 2

输入

4
5 5
10 1 8 -1
12 3 13 0
18 3 17 0
20 1 22 -1
25 5

输出

22.80624847

样例 3

输入

3
0 0
3 -1 2 1
8 0 8 1
5 -1 5 1
0 2

输出

16.144380531