AT_agc023_d.[AGC023D] Go Home

有 $N$ 栋公寓楼排成一条数轴，每栋楼编号为 $1$ 到 $N$。第 $i$ 栋公寓楼位于坐标 $X_i$。AtCoder 公司位于坐标 $S$。所有 AtCoder 公司的员工都住在这 $N$ 栋公寓中的某一栋。住在第 $i$ 栋公寓的员工人数为 $P_i$。

现在，所有员工准备同时回家。他们因为工作很累，都希望乘坐公司拥有的巴士回家。公司只有一辆巴士，但可以容纳所有员工。这辆巴士会载着所有员工，从坐标 $S$ 出发，并按照如下规则行驶：

• 所有乘客（巴士为自动驾驶，无司机）投票决定向正方向还是负方向前进。每位员工有一票，不能弃权。得票多的方向前进 $1$ 单位距离。如果票数相同，则向负方向前进。如果移动后的位置有公寓楼，则该楼的所有住户下车。
• 只要巴士上还有员工，就重复上述操作。

具体例子请参考样例 $1$ 的说明。

巴士每前进 $1$ 单位距离需要 $1$ 秒。投票和下车所需时间可忽略不计。

每位员工都会选择使自己下车所需时间最短的投票方式。更严格地说，在每次投票时，每位员工都会考虑，巴士若向哪个方向前进，自己能更快回家（假设之后所有人都采用最优策略）。员工会基于这些信息做出最优选择。如果无论巴士向哪个方向前进，自己回家的时间都一样，则投票给负方向。

请你计算，从巴士出发到最后一名员工下车所需的总时间。已知给定的公寓位置、住户人数和巴士位置时，巴士的行驶路线是唯一确定的。此外，可以证明所有员工都能在有限时间内回家。

输入通过标准输入给出，格式如下：

$N$ $S$ $X_1$ $P_1$ $X_2$ $P_2$ $\cdots$ $X_N$ $P_N$

输出从巴士出发到最后一名员工下车所需的总时间。

限制条件

• $1 \leq N \leq 10^5$
• $1 \leq S \leq 10^9$
• $1 \leq X_1 < X_2 < \cdots < 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$）
• 所有输入均为整数。

样例解释 1

假设巴士最初向负方向移动，则巴士坐标变化为 $2 \to 1$，第 $1$ 栋公寓的住户下车。之后巴士的移动路线很明显，会一直向正方向移动。因此，若最初向负方向移动，巴士坐标变化为 $2 \to 1 \to 2 \to 3 \to 4$，第 $1$、$2$、$3$ 栋公寓住户分别在 $1$ 秒、$3$ 秒、$4$ 秒下车。

若最初向正方向移动，则巴士坐标变化为 $2 \to 3$，第 $2$ 栋公寓住户下车。之后巴士会转向第 $1$ 栋公寓，因为第 $1$ 栋住户人数多于第 $3$ 栋。巴士到达第 $1$ 栋后，再前往第 $3$ 栋。因此，若最初向正方向移动，巴士坐标变化为 $2 \to 3 \to 2 \to 1 \to 2 \to 3 \to 4$，第 $1$、$2$、$3$ 栋公寓住户分别在 $3$ 秒、$1$ 秒、$6$ 秒下车。

因此，第 $1$、$3$ 栋住户会选择让巴士最初向负方向移动，第 $2$ 栋住户会选择正方向。第 $1$、$3$ 栋住户共 $3+2=5$ 人，多于第 $2$ 栋的 $4$ 人。因此，巴士最初会向负方向移动，坐标变化为 $2 \to 1 \to 2 \to 3 \to 4$。

样例解释 2

由于各公寓住户人数相差极大，巴士总是会朝住户最多的公寓方向前进。

由 ChatGPT 4.1 翻译