/ 
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 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
出力
バスが出発してから最後に社員がバスを降りるまでにかかる時間が何秒かを出力せよ。
入力例 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
Score : 1200 points
Problem Statement
There are N apartments along a number line, numbered 1 through N. Apartment i is located at coordinate X_i. Also, the office of AtCoder Inc. is located at coordinate S. Every employee of AtCoder lives in one of the N apartments. There are P_i employees who are living in Apartment i.
All employees of AtCoder are now leaving the office all together. Since they are tired from work, they would like to get home by the company's bus. AtCoder owns only one bus, but it can accommodate all the employees. This bus will leave coordinate S with all the employees and move according to the following rule:
-
Everyone on the bus casts a vote on which direction the bus should proceed, positive or negative. (The bus is autonomous and has no driver.) Each person has one vote, and abstaining from voting is not allowed. Then, the bus moves a distance of 1 in the direction with the greater number of votes. If a tie occurs, the bus moves in the negative direction. If there is an apartment at the coordinate of the bus after the move, all the employees who live there get off.
-
Repeat the operation above as long as there is one or more employees on the bus.
For a specific example, see Sample Input 1.
The bus takes one seconds to travel a distance of 1. The time required to vote and get off the bus is ignorable.
Every employee will vote so that he himself/she herself can get off the bus at the earliest possible time. Strictly speaking, when a vote is taking place, each employee see which direction results in the earlier arrival at his/her apartment, assuming that all the employees follow the same strategy in the future. Based on this information, each employee makes the optimal choice, but if either direction results in the arrival at the same time, he/she casts a vote to the negative direction.
Find the time the bus will take from departure to arrival at the last employees' apartment. It can be proved that, given the positions of the apartments, the numbers of employees living in each apartment and the initial position of the bus, the future movement of the bus is uniquely determined, and the process will end in a finite time.
Constraints
- 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 )
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N S X_1 P_1 X_2 P_2 : X_N P_N
Output
Print the number of seconds the bus will take from departure to arrival at the last employees' apartment.
Sample Input 1
3 2 1 3 3 4 4 2
Sample Output 1
4
Assume that the bus moves in the negative direction first. Then, the coordinate of the bus changes from 2 to 1, and the employees living in Apartment 1 get off. The movement of the bus after that is obvious: it just continues moving in the positive direction. Thus, if the bus moves in the negative direction first, the coordinate of the bus changes as 2 → 1 → 2 → 3 → 4 from departure. The time it takes to get home for the employees living in Apartment 1, 2, 3 are 1, 3, 4 seconds, respectively.
Next, assume that the bus moves in the positive direction first. Then, the coordinate of the bus changes from 2 to 3, and the employees living in Apartment 2 get off. Afterwards, the bus starts heading to Apartment 1, because there are more employees living in Apartment 1 than in Apartment 3. Then, after arriving at Apartment 1, the bus heads to Apartment 3. Thus, if the bus moves in the positive direction first, the coordinate of the bus changes as 2 → 3 → 2 → 1 → 2 → 3 → 4 from departure. The time it takes to get home for the employees living in Apartment 1, 2, 3 are 3, 1, 6 seconds, respectively.
Therefore, in the beginning, the employees living in Apartment 1 or 3 will try to move the bus in the negative direction. On the other hand, the employees living in Apartment 2 will try to move the bus in the positive direction in the beginning. There are a total of 3 + 2 = 5 employees living in Apartment 1 and 3 combined, which is more than those living in Apartment 2, which is 4. Thus, the bus will move in the negative direction first, and the coordinate of the bus will change as 2 → 1 → 2 → 3 → 4 from departure.
Sample Input 2
6 4 1 10 2 1000 3 100000 5 1000000 6 10000 7 100
Sample Output 2
21
Since the numbers of employees living in different apartments are literally off by a digit, the bus consistently head to the apartment where the most number of employees on the bus lives.
Sample Input 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
Sample Output 3
2397671583