配点 : $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$

出力

答えを出力せよ。

2 3
2 1
5 10

4

太郎君は以下のように動きます:

• 村 $0$ から村 $1$ へ $1$ 円払って移動する。所持金は $2$ 円となる。
• 村 $1$ から村 $2$ へ $1$ 円払って移動する。所持金は $1$ 円となる。
• 村 $2$ で $1$ 人目の友達から $1$ 円受け取り、所持金は $2$ 円となる。
• 村 $2$ から村 $3$ へ $1$ 円払って移動する。所持金は $1$ 円となる。
• 村 $3$ から村 $4$ へ $1$ 円払って移動する。所持金は $0$ 円となり、この村には友達もいないため村 $4$ で止まる。

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

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

6000000000

答えが $32$ bit 整数に収まらないことがある事に注意してください。

3 2
5 5
2 1
2 2

10

同じ村に複数の友達がいる可能性もあります。