No.817 Coin donation
タグ : / 解いたユーザー数 213
作問者 :
Enjapma_kyopro
/ テスター :
tempura_pp
問題文
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
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。