/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 400 点
問題文
高橋君はイベント会場の音響担当です。会場には一直線の通路があり、通路沿いに N 個のブースが並んでいます。各ブースにアナウンスの音声を届ける必要があります。
通路上の位置は座標で表します。ブース i は座標 X_i の位置にあり、音声が聞こえたと判断されるために必要な音量の合計値（聴取閾値）は D_i です。
高橋君は通路上の好きな整数座標の位置 P（任意の整数）をちょうど 1 つ選び、そこにスピーカーを設置します。スピーカーの設置位置は 1 箇所のみであり、途中で位置を変えることはできません。
スピーカーを 1 回鳴らすと、その出力音量は V です。位置 P に設置されたスピーカーからブース i に届く音量は、1 回あたり \max(V - |X_i - P|, 0) です。つまり、スピーカーとブースの距離が離れるほど音量が減衰し、距離が V 以上のブースには音は届きません。
スピーカーを同じ位置で K 回（K は正の整数）鳴らすと、各ブース i に届く音量の合計は K \times \max(V - |X_i - P|, 0) となります。ブース i に音声が届いたと判断されるためには、この合計が聴取閾値 D_i 以上である必要があります。
すべてのブースに音声を届けるためには、すべてのブース i（1 \leq i \leq N）について同時に上の条件を満たす必要があります。このため、スピーカーの位置 P から距離 V 以上離れたブースが 1 つでも存在すると、そのブースには何回鳴らしても音量が届かず、条件を満たすことができません。
高橋君はスピーカーを鳴らす回数をできるだけ少なくしたいと考えています。スピーカーの設置位置 P を最適に選んだとき、すべてのブースに音声を届けるために必要なスピーカーを鳴らす最小回数 K を求めてください。
ただし、どの整数座標にスピーカーを設置しても、すべてのブースに音声を届けることが不可能な場合は -1 を出力してください。
制約
- 1 \leq N \leq 2 \times 10^5
- 1 \leq V \leq 10^9
- 0 \leq X_i \leq 10^9
- 1 \leq D_i \leq 10^{18}
- X_i はすべて異なる
- 入力はすべて整数である
入力
N V X_1 D_1 X_2 D_2 : X_N D_N
- 1 行目には、ブースの個数を表す整数 N と、スピーカーの 1 回あたりの出力音量を表す整数 V が、スペース区切りで与えられる。
- 2 行目から N + 1 行目では、各ブースの位置と聴取閾値が与えられる。
- 1 + i 行目では、ブース i の座標 X_i と聴取閾値 D_i が整数としてスペース区切りで与えられる。
出力
すべてのブースに音声を届けるために必要なスピーカーを鳴らす最小回数を 1 行で出力せよ。すべてのブースに音声を届けることが不可能な場合は -1 を出力せよ。
入力例 1
3 5 0 4 3 6 7 2
出力例 1
2
入力例 2
2 3 0 10 6 10
出力例 2
-1
入力例 3
8 10 100 15 102 80 105 21 108 100 111 70 113 42 116 18 118 55
出力例 3
55
入力例 4
30 100 5000 1000000000000 5006 123456789012 5012 987654321098 5018 555555555555 5024 314159265358 5030 271828182845 5036 777777777777 5042 888888888888 5048 999999999999 5054 111111111111 5060 222222222222 5066 333333333333 5072 444444444444 5078 666666666666 5084 135791357913 5090 246802468024 5096 101010101010 5102 909090909090 5108 123123123123 5114 456456456456 5120 789789789789 5126 100000000000 5132 200000000000 5138 300000000000 5144 400000000000 5150 500000000000 5156 600000000000 5162 700000000000 5168 800000000000 5174 900000000000
出力例 4
75000000000
入力例 5
1 1 1000000000 1000000000000000000
出力例 5
1000000000000000000
Score : 400 pts
Problem Statement
Takahashi is in charge of audio for an event venue. The venue has a straight corridor, and N booths are lined up along the corridor. He needs to deliver announcement audio to each booth.
Positions along the corridor are represented by coordinates. Booth i is located at coordinate X_i, and the total sound volume required for the audio to be considered audible (hearing threshold) is D_i.
Takahashi will choose exactly one integer coordinate position P (any integer) on the corridor and place a speaker there. There is only one speaker placement location, and the position cannot be changed afterwards.
When the speaker is sounded once, its output volume is V. The volume that reaches booth i from a speaker placed at position P is \max(V - |X_i - P|, 0) per sounding. In other words, the volume attenuates as the distance between the speaker and the booth increases, and no sound reaches booths at a distance of V or more.
When the speaker is sounded K times (K is a positive integer) at the same position, the total volume reaching each booth i is K \times \max(V - |X_i - P|, 0). For booth i to be considered as having received the audio, this total must be at least the hearing threshold D_i.
To deliver audio to all booths, the above condition must be satisfied simultaneously for all booths i (1 \leq i \leq N). Therefore, if even one booth exists at a distance of V or more from the speaker position P, no amount of soundings can deliver volume to that booth, making it impossible to satisfy the condition.
Takahashi wants to minimize the number of times the speaker is sounded. Find the minimum number of times K the speaker must be sounded to deliver audio to all booths, when the speaker placement position P is chosen optimally.
However, if it is impossible to deliver audio to all booths regardless of which integer coordinate the speaker is placed at, output -1.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 1 \leq V \leq 10^9
- 0 \leq X_i \leq 10^9
- 1 \leq D_i \leq 10^{18}
- All X_i are distinct
- All input values are integers
Input
N V X_1 D_1 X_2 D_2 : X_N D_N
- The first line contains an integer N representing the number of booths and an integer V representing the output volume per sounding of the speaker, separated by a space.
- From the 2nd line to the (N + 1)-th line, the position and hearing threshold of each booth are given.
- The (1 + i)-th line contains the coordinate X_i and hearing threshold D_i of booth i as integers separated by a space.
Output
Output in one line the minimum number of times the speaker must be sounded to deliver audio to all booths. If it is impossible to deliver audio to all booths, output -1.
Sample Input 1
3 5 0 4 3 6 7 2
Sample Output 1
2
Sample Input 2
2 3 0 10 6 10
Sample Output 2
-1
Sample Input 3
8 10 100 15 102 80 105 21 108 100 111 70 113 42 116 18 118 55
Sample Output 3
55
Sample Input 4
30 100 5000 1000000000000 5006 123456789012 5012 987654321098 5018 555555555555 5024 314159265358 5030 271828182845 5036 777777777777 5042 888888888888 5048 999999999999 5054 111111111111 5060 222222222222 5066 333333333333 5072 444444444444 5078 666666666666 5084 135791357913 5090 246802468024 5096 101010101010 5102 909090909090 5108 123123123123 5114 456456456456 5120 789789789789 5126 100000000000 5132 200000000000 5138 300000000000 5144 400000000000 5150 500000000000 5156 600000000000 5162 700000000000 5168 800000000000 5174 900000000000
Sample Output 4
75000000000
Sample Input 5
1 1 1000000000 1000000000000000000
Sample Output 5
1000000000000000000