C - Friends and Travel costs 解説 /

実行時間制限: 2 sec / メモリ制限: 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.