307004 - 巡逻线路

巡逻队需要每天对工程的n个关键区域进行巡视检查,简言之,就是在平面中有n个点,记横坐标最小的点为A,最大的点为B,巡逻队需要找到一条在每个点经过一次(A点两次)的情况下从A走到B,再回到A的最短路径。限制条件是:

  1. 从A走到B时,只能由横坐标小的点走到大的点;
  2. 由B回到A时,只能由横坐标大的点走到小的点;
  3. 有两个关键点b_1,b_2b_10n-1的路上,b_2n-10的路上。

输入

第一行三个整数n,b_1,b_2(n≤1 000,0<b_1,b_2<n-1b_1≠b_2)n表示区域数,从 0n-1编号,b_1b_2为两个关键点的编号。

随后n行,每行两个整数xy表示该点的坐标(0≤x,y≤2 000),从0号点顺序给出。

所有点横坐标不同,并已按x增序排序。

输出

输出最短路径长度(精确到小数点后面2位)。

样例

输入

5 1 3
1 3
3 4
4 1
7 5
8 3

输出

18.18

提示

最短路径:0→1→4→3→2→0

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题