問題一覧 > 通常問題

No.817 Coin donation

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 211
作問者 : Enjapma_kyoproEnjapma_kyopro / テスター : tempura_pptempura_pp
10 ProblemId : 2439 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2019-04-22 12:55:44

問題文

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もしくは右上の雲マークをクリックしてアカウントを作成してください。