No.817 Coin donation

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 114
作問者 : Enjapma_kyoproEnjapma_kyopro / テスター : tempura_pptempura_pp
5 ProblemId : 2439 / 出題時の順位表

問題文

Enjapma 王国では、 $1$ 円玉から $10^9$ 円玉まで、$10^9$ 種類の硬貨が流通しています。硬貨の金額は全て整数です。

何も入っていない募金箱があります。心優しいあなたはこの箱に対して、 $N$ 回の操作を行います。
$i$ 回目の操作では、 $A_i$ 円玉から $B_i$ 円玉の全ての硬貨を、箱に $1$ 枚ずつ入れていきます。

$N$ 回の操作を終えた後、箱の中にある硬貨で、その金額が $K$ 番目に安い硬貨は何でしょう?

入力

$N \ K$
$A_1$ $B_1$
$A_2$ $B_2$
:
$A_N$ $B_N$

$1 \le N \le 10^5$
$1 \le K \le min(10^9 , $ 最終的に箱の中にある硬貨の数$)$
$1 \le A_i \le 10^9$
$1 \le B_i \le 10^9$
$A_i \le B_i$
入力はすべて整数

出力

操作を終えた後の、 箱の中で $K$ 番目に安い硬貨の金額を出力してください。 最後に改行してください。

サンプル

サンプル1
入力
3 6
1 4
2 5
1 6
出力
3

箱の中には、$1$ 円玉が $2$ 枚、$2$ 円玉が $3$ 枚、$3$ 円玉が $3$ 枚、$4$ 円玉が $3$ 枚、$5$ 円玉が $2$ 枚、$6$ 円玉が $1$ 枚入っています。
この中で $6$ 番目に安い硬貨は $3$ 円玉です。

サンプル2
入力
14 159265
35 897
932 3846
264 338
327 950288
419 716
939 9375
105 82097
49 44592
307 81640
628 6208998
6280 348253
4211 7067
982 14808
651 3282
出力
22509

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。