题目描述

农夫约翰为奶牛们建造了一个障碍训练场地。这个场地由一系列 (N) 个（(1 ≤ N ≤ 50000)）长度各异的栅栏组成，每个栅栏都平行于 (x) 轴。栅栏 (i) 的 (y) 坐标是 (i) 。

约翰谷仓的门位于原点（如下标记为“(*)”）。训练场地的起点位于坐标 ((S,N)) 。

   +-S-+-+-+        (fence #N)
 +-+-+-+            (fence #N-1)
     ...               ...
   +-+-+-+          (fence #2)
     +-+-+-+        (fence #1)
=|=|=|=*=|=|=|      (barn)
-3-2-1 0 1 2 3     

约翰最初的想法是让奶牛跳过这些栅栏，但奶牛们更愿意四蹄着地行走。因此，它们会沿着栅栏走，当走到栅栏尽头时，它们会朝着 \(x\) 轴方向继续直线行走，直到碰到另一段栅栏或者谷仓的边缘。然后它们决定向左或向右走，直到到达那段栅栏的尽头，如此反复，直到最终到达谷仓的边缘，然后可能再走一小段路，到达终点。

自然地，奶牛们希望行走的路程尽可能短。请找出奶牛从起点走到谷仓门所需要来回行走的最小距离。

输入

第 1 行：两个用空格分隔的整数：(N) 和 (S)（(-100000 ≤ S ≤ 100000)）

第 2 行到 (N + 1) 行：每行包含两个用空格分隔的整数：(A_i) 和 (B_i)（(-100000 ≤ A_i < B_i ≤ 100000)），表示栅栏段 (i) 的起始和结束 (x) 坐标。第 2 行描述栅栏 #1；第 3 行描述栅栏 #2；依此类推。起点位置将满足 (A_N ≤ S ≤ B_N)。注意，栅栏将按照输入顺序的逆序进行遍历。

输出

第 1 行：从起点到终点，通过绕着栅栏行走，在 (x) 方向上来回所需的最小距离。在 (y) 方向上的距离不计算在内，因为它总是恰好为 (N) 。

4 0 
-2 1
-1 2
-3 0
-2 1

4

提示

这个问题的输入数据量很大，请使用 scanf() 而不是 cin 来读取数据，以避免超时。

输入细节

   +-+-S-+             Fence 4
 +-+-+-+               Fence 3
     +-+-+-+           Fence 2
   +-+-+-+             Fence 1
 |=|=|=*=|=|=|         Barn
-3-2-1 0 1 2 3      

输出细节：正向走一个单位（到 ((1,4))），然后朝着谷仓走，轻松绕过栅栏 3 。再正向走一个单位（到 ((2,2))），然后走到谷仓的边缘。再朝着原点走两个单位，总共在 (x) 方向上来回走了 4 个单位。

来源

USACO 2004 年 12 月金牌赛