Contest Duration: - (local time) (100 minutes) Back to Home
C - Friends and Travel costs /

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

10^{100}+1 個の村があり、それぞれ村 0, 村 1, \ldots, 村 10^{100} と番号がついています。
0 以上 10^{100}-1 以下の全ての整数 i について、村 i1 円を払う事で村 (i+1) に移動することができます。 それ以外の移動方法はありません。

### 制約

• 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 から村 11 円払って移動する。所持金は 2 円となる。
• 1 から村 21 円払って移動する。所持金は 1 円となる。
• 21 人目の友達から 1 円受け取り、所持金は 2 円となる。
• 2 から村 31 円払って移動する。所持金は 1 円となる。
• 3 から村 41 円払って移動する。所持金は 0 円となり、この村には友達もいないため村 4 で止まる。

よって、 4 を出力します。

### 入力例 2

5 1000000000
1 1000000000
2 1000000000
3 1000000000
4 1000000000
5 1000000000


### 出力例 2

6000000000


### 入力例 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


### 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.