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的路上。

Input

第一行三个整数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增序排序。

Output

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

Examples

Input

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

Output

18.18

Hint

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

Time Limit 1 second
Memory Limit 128 MB
Discuss Stats
上一题 下一题