← 返回题目列表

AtCoder · agc023_d

D. 回家

中文机器翻译题面 查看原题

分数: 1200 点

问题陈述

有 N 沿着数轴的公寓,已编号 1 通过 N。 公寓 i 位于坐标 X_i。 此外,AtCoder Inc. 的办公室位于坐标 S。 AtCoder 的每位员工都居住在其中一间 N 公寓。 有 P_i 住在公寓的员工 i.

AtCoder 的所有员工现在一起离开办公室。 由于工作累了,他们想乘坐公司的公交车回家。 AtCoder只拥有一辆巴士,但可以容纳所有员工。 这辆巴士将离开坐标 S 与全体员工一起并按照以下规则搬迁:

  • 公交车上的每个人都对公交车应朝哪个方向行驶进行投票,无论是正方向还是负方向。 (公交车是自主的,没有司机。)每人一票,不允许弃权。然后,公交车移动了一段距离 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 to 1,以及住在公寓的员工 1 下车。 此后巴士的运动是显而易见的:它只是继续朝正方向运动。 因此,如果公交车首先沿负方向移动,则公交车的坐标变化为 2 → 1 → 2 → 3 → 4 从出发。 居住在公寓的员工回家所需时间 分别为 1, 2, 3 是 1, 3, 4 秒。

接下来,假设公交车首先沿正方向移动。 然后,总线的坐标从 2 to 3,以及住在公寓的员工 2 下车。 随后,巴士开始前往公寓 1,因为公寓里住的员工比较多 1 比在公寓里 3。 然后,到达公寓后 1, 巴士前往公寓 3。 因此,如果公交车首先沿正方向移动,则公交车的坐标变化为 2 → 3 → 2 → 1 → 2 → 3 → 4 从出发。 居住在公寓的员工回家所需时间 分别为 1, 2, 3 是 3, 1, 6 秒。

因此,一开始,住在公寓的员工 1 or 3 将尝试向负方向移动总线。 另一方面,住在公寓里的员工 2 一开始会尝试将总线朝正方向移动。 总共有 3 + 2 = 5 住在公寓的员工 1 和 3 加起来,比住在公寓的人还要多 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