配点 : $1200$ 点

問題文

$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 社を出発してから、最後に社員がバスを降りるまでにかかる時間が何秒かを求めてください。 なお、マンションの位置、住人の数、バスの位置が与えられたとき、バスがどのように動くかは一意に定まることが証明できます。 また、有限時間にすべての社員が帰宅することも証明できます。

制約

• $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$

出力

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

3 2
1 3
3 4
4 2

4

最初にバスが負の方向へ動いたとしましょう。 すると、バスの座標は $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$ と変化することになります。

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