「Fence Obstacle Course」围栏障碍训练场

农夫约翰为他的奶牛们建造了一个围栏障碍训练场，以供奶牛们玩耍。

训练场由N个不同长度的围栏组成，每个围栏都与x轴平行，并且第i个围栏的y坐标为i。

训练场的出口位于原点，起点位于（S,N）

   +-S-+-+-+        (fence #N)

 +-+-+-+            (fence #N-1)

     ...               ...

   +-+-+-+          (fence #2)

     +-+-+-+        (fence #1)

=|=|=|=*=|=|=|      (barn)

-3-2-1 0 1 2 3

这些牛会从起点处开始向下走，当它们碰到围栏时会选择沿着围栏向左或向右走，走到围栏端点时继续往下走，按照此种走法一直走到出口为止。

请问，这些牛从开始到结束，行走的水平距离最少为多少。

输入格式

第一行包含两个整数N和S。

第2…N+1行，每行包含两个整数 $A_i,B_i$ ,表示一个围栏的起始横坐标和结束横坐标，其中第i+1行表示第i个围栏的数据。

起点坐标满足 $A_N \le S \le B_N$ 。

输出格式

输出一个整数，表示最小水平行走距离。

数据范围

$1 \le N \le 30000$ ,
$-100000 \le S \le 100000$ ,
$-100000 \le A_i,B_i \le 100000$

输入样例：

输出样例：

来源

《算法竞赛进阶指南》
acwing 可能含有视频讲解