/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
10^{100}+1 個の村があり、それぞれ村 0, 村 1, \ldots, 村 10^{100} と番号がついています。
0 以上 10^{100}-1 以下の全ての整数 i について、村 i で 1 円を払う事で村 (i+1) に移動することができます。
それ以外の移動方法はありません。
太郎君は初め K 円を持った状態で村 0 におり、その後、可能な限り大きな番号の村まで進もうとします。
太郎君には N 人の友達がいます。i 人目の友達は村 A_i にいて、太郎君が村 A_i に着いたときに B_i 円を太郎君に渡します。
太郎君が最終的にたどり着く村の番号を求めてください。
制約
- 1 \leq N \leq 2\times 10^5
- 1 \leq K \leq 10^9
- 1 \leq A_i \leq 10^{18}
- 1 \leq B_i \leq 10^9
- 入力は全て整数である。
入力
入力は以下の形式で標準入力から与えられる。
N K A_1 B_1 : A_N B_N
出力
答えを出力せよ。
入力例 1
2 3 2 1 5 10
出力例 1
4
太郎君は以下のように動きます:
- 村 0 から村 1 へ 1 円払って移動する。所持金は 2 円となる。
- 村 1 から村 2 へ 1 円払って移動する。所持金は 1 円となる。
- 村 2 で 1 人目の友達から 1 円受け取り、所持金は 2 円となる。
- 村 2 から村 3 へ 1 円払って移動する。所持金は 1 円となる。
- 村 3 から村 4 へ 1 円払って移動する。所持金は 0 円となり、この村には友達もいないため村 4 で止まる。
よって、 4 を出力します。
入力例 2
5 1000000000 1 1000000000 2 1000000000 3 1000000000 4 1000000000 5 1000000000
出力例 2
6000000000
答えが 32 bit 整数に収まらないことがある事に注意してください。
入力例 3
3 2 5 5 2 1 2 2
出力例 3
10
同じ村に複数の友達がいる可能性もあります。
Score : 300 points
Problem Statement
There are 10^{100}+1 villages, labeled with numbers 0, 1, \ldots, 10^{100}.
For every integer i between 0 and 10^{100}-1 (inclusive), you can pay 1 yen (the currency) in Village i to get to Village (i + 1).
There is no other way to travel between villages.
Taro has K yen and is in Village 0 now. He will try to get to a village labeled with as large a number as possible.
He has N friends. The i-th friend, who is in Village A_i, will give Taro B_i yen when he reaches Village A_i.
Find the number with which the last village he will reach is labeled.
Constraints
- 1 \leq N \leq 2\times 10^5
- 1 \leq K \leq 10^9
- 1 \leq A_i \leq 10^{18}
- 1 \leq B_i \leq 10^9
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N K A_1 B_1 : A_N B_N
Output
Print the answer.
Sample Input 1
2 3 2 1 5 10
Sample Output 1
4
Takahashi will travel as follows:
- Go from Village 0 to Village 1, for 1 yen. Now he has 2 yen.
- Go from Village 1 to Village 2, for 1 yen. Now he has 1 yen.
- Get 1 yen from the 1-st friend in Village 2. Now he has 2 yen.
- Go from Village 2 to Village 3, for 1 yen. Now he has 1 yen.
- Go from Village 3 to Village 4, for 1 yen. Now he has 0 yen, and he has no friends in this village, so his journey ends here.
Thus, we should print 4.
Sample Input 2
5 1000000000 1 1000000000 2 1000000000 3 1000000000 4 1000000000 5 1000000000
Sample Output 2
6000000000
Note that the answer may not fit into a 32-bit integer.
Sample Input 3
3 2 5 5 2 1 2 2
Sample Output 3
10
He may have multiple friends in the same village.