问题描述

有一条数轴上有 N 个公寓，分别编号为 1 到 N。公寓 i 的坐标为 X_i。AtCoder 公司的办公室位于坐标 S。AtCoder 公司的每个员工都住在这 N 个公寓中的一个。有 P_i 名员工住在公寓 i 中。

现在，所有的 AtCoder 员工都一起离开办公室。因为他们工作累了，所以他们想要乘坐公司的巴士回家。AtCoder 只拥有一辆巴士，但它可以容纳所有的员工。这辆巴士将与所有的员工一起从坐标 S 处出发，并按照以下规则行动：

• 巴士上的每个人都对巴士应该向哪个方向前进进行投票，正向还是负向。（巴士是自主的，没有司机。）每个人有一票，不允许弃权。然后，巴士朝得票数较多的方向移动 1 个单位距离。如果出现平票，则巴士向负方向移动。如果巴士在移动后抵达公寓的位置上，则住在那里的所有员工下车。

• 只要巴士上还有一个或多个员工，就重复上述操作。

请参见样例输入 1，查看一个具体的示例。

巴士需要花费 1 秒钟来移动 1 个单位距离。投票和下车所需的时间可以忽略不计。

每个员工将投票以便他/她能够尽快下巴士。严格来说，当进行投票时，每位员工会查看哪个方向会使他/她尽早到达自己的公寓，并假设所有员工在未来都会采取相同的策略。根据这一信息，每个员工做出最优选择，但如果两个方向的到达时间相同，则投给负方向。

找出巴士从出发到最后一位员工的公寓抵达所需的时间。可以证明，给定公寓位置、每个公寓中住着的员工数和巴士的初始位置，巴士的未来移动是唯一确定的，并且过程将在有限时间内结束。

约束条件

• $1 \leq N \leq 10^5$
• $1 \leq S \leq 10^9$
• $1 \leq X_1 < X_2 < ... < X_N \leq 10^9$
• $X_i \neq S$ ($1 \leq i \leq N$)
• $1 \leq P_i \leq 10^9$ ($1 \leq i \leq N$)
• 输入中的所有值都是整数。

输入格式

从标准输入读入数据，格式如下：

N S
X_1 P_1
X_2 P_2
...
X_N P_N

输出格式

输出巴士从出发到最后一位员工的公寓抵达所需的秒数。

示例输入 1

3 2
1 3
3 4
4 2

示例输出 1

4

假设巴士首先向负方向移动。那么巴士的坐标会从 2 变为 1，并且住在公寓 1 中的员工下车。之后，巴士的移动是显而易见的：它只会继续向正方向移动。因此，如果巴士首先向负方向移动，则巴士的坐标在出发时会变为 2 → 1 → 2 → 3 → 4。公寓 1、2 和 3 中的员工到家所需的时间分别为 1、3、4 秒。

接下来，假设巴士首先向正方向移动。那么巴士的坐标会从 2 变为 3，并且住在公寓 2 中的员工下车。之后，巴士开始朝公寓 1 前进，因为公寓 1 中的员工比公寓 3 中的员工多。然后，在抵达公寓 1 后，巴士前往公寓 3。因此，如果巴士首先向正方向移动，则巴士的坐标在出发时会变为 2 → 3 → 2 → 1 → 2 → 3 → 4。公寓 1、2 和 3 中的员工到家所需的时间分别为 3、1、6 秒。

因此，最初，公寓 1 或 3 中的员工将尝试让巴士向负方向移动。另一方面，住在公寓 2 中的员工将在一开始尝试让巴士向正方向移动。公寓 1 和 3 中一共有 3 + 2 = 5 名员工居住，这比住在公寓 2 中的员工数目（4 名）更多。因此，巴士将首先向负方向移动，并且巴士的坐标将从出发时的 2 变为 1 → 2 → 3 → 4。

示例输入 2

6 4
1 10
2 1000
3 100000
5 1000000
6 10000
7 100

示例输出 2

21

由于住在不同公寓中的员工人数差别很大，巴士总是朝着巴士上员工人数最多的公寓前进。

示例输入 3

15 409904902
94198000 15017
117995501 7656764
275583856 313263626
284496300 356635175
324233841 607
360631781 148
472103717 5224
497641071 34695
522945827 816241
554305668 32
623788284 22832
667409501 124410641
876731548 12078
904557302 291749534
918215789 5

示例输出 3

2397671583