[AGC023D] Go Home

一条街上有 $N$ 栋楼，位置从小到大分别在 $X_1, X_2, \ldots , X_N$。 在位置 $S$ 有一座公司，员工下班时乘坐公司的员工班车回家。 这些员工住在 $N$ 栋楼内，具体地说，第 $i$ 栋楼内住着 $P_i$ 个员工。 班车是自动驾驶的，每一个时刻，还在车内的每个员工都会进行投票，只能投正方向或者负方向，不能弃权。 班车会自动统计两个方向的票数，并且往票多的方向行驶一个单位长度，如果票一样多，那就往负方向行驶。 员工们也有投票策略，每一个员工都会投能让他回家时间尽量早的方向，如果两个方向一样早，那就投负方向。 如果班车到达了某一个楼，那么住在那栋楼中的所有员工都会下车。 可以证明，在上述条件下，每个员工投票的方向是能够唯一确定的，班车的运行路线也能够唯一确定。 最终询问最后一名员工回到家，经过了多少个单位时间。可以证明答案在 `long long` 范围内。 - $1 \le N \le {10}^5$，$1 \le X_1 < X_2 < \cdots < X_N \le {10}^9$，$1 \le P_i \le {10}^9$，$1 \le S \le {10}^9$，$S \ne X_i$。

[problemUrl]: https://atcoder.jp/contests/agc023/tasks/agc023_d $ N $ 棟のマンションが数直線上に並んでおり、$ 1 $ から $ N $ までの番号がついています。 マンション $ i $ は座標 $ X_i $ の位置にあります。 また、AtCoder 社は座標 $ S $ の位置にあります。 AtCoder 社の社員は皆、$ N $ 棟のうちいずれかのマンションに住んでいます。 マンション $ i $ に住んでいる社員の人数は $ P_i $ です。 いま、AtCoder 社の社員全員が、一斉に帰宅しようとしています。 彼らは仕事で疲れているため、AtCoder 社の所有するバスでの帰宅を望んでいます。 AtCoder 社の所有するバスは $ 1 $ 台しかありませんが、社員全員を乗せることができます。 このバスは、社員全員を乗せて座標 $ S $ から出発し、次のようなルールで動きます。 - バスに乗っている全員（このバスは自動運転であり、運転手はいないものとする）で、正の方向へ進むか負の方向へ進むかの投票を行う。 各社員 $ 1 $ 票ずつ投票し、棄権は許されない。 その後、得票数の多い方向へ、距離 $ 1 $ だけ移動する。 なお、得票数が同じ場合は、負の方向へ移動する。 もし移動した後の座標にマンションがあるなら、そこに住む社員全員が降りる。 - バスに社員が乗っている限り、上の操作を繰り返す。 具体例については、入出力例 $ 1 $ の説明を参照してください。 バスは、距離 $ 1 $ 進むのにちょうど $ 1 $ 秒かかります。 また、投票や降車にかかる時間は無視できます。 AtCoder 社の社員は全員、自分がバスを降りるまでの時間を最小化するように投票します。 厳密にいうと、ある投票の際には、各社員は、バスがどちらに動いたとき自分の帰宅が早いか (社員全員が今後同じ戦略に従うとして) 考えます。 各社員は、この情報をもとに最適な選択を行いますが、バスがどちらの方向に動いても帰宅までの時間が変わらないときは、負の方向へ投票します。 この時、バスが AtCoder 社を出発してから、最後に社員がバスを降りるまでにかかる時間が何秒かを求めてください。 なお、マンションの位置、住人の数、バスの位置が与えられたとき、バスがどのように動くかは一意に定まることが証明できます。 また、有限時間にすべての社員が帰宅することも証明できます。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ S $ $ X_1 $ $ P_1 $ $ X_2 $ $ P_2 $ $ : $ $ X_N $ $ P_N $

バスが出発してから最後に社員がバスを降りるまでにかかる時間が何秒かを出力せよ。

3 2
1 3
3 4
4 2

4

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

21

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

2397671583

### 制約 - $ 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 $ ) - 入力はすべて整数である。 ### Sample Explanation 1 最初にバスが負の方向へ動いたとしましょう。 すると、バスの座標は $ 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 $ と変化することになります。 ### Sample Explanation 2 それぞれのマンションに住む人数が文字通り桁違いなので、バスは常に、バスに乗っている住人の数が最も多いマンションへと向かいます。