[ABC061C] Big Array

## 题目翻译 ### 题目描述 有一个数组S，一开始是空的。接下来对这个数组进行N次插入操作. 第ii次操作会向数组中加入$b_i$ 个整数$a_i$ ，然后将整个数组从小到大排一次序。 求N次操作后, 数组中的第K个数。 例如S=\{1,2,2,3,3,3\}时, 从小到大排序后第4个数是3。 ### 输入格式 第1行, 包含两个整数N,K用空格分隔. 第2行到第N+1行, 每行包含两个整数 $a_i$,$b_i$ ### 输出格式 输出N次操作后集合中第K小的数. ### 说明/提示 #### 数据范围 * 1≦N≦$10^5$ * 1≦$a_i$ ,$b_i$ ≦$10^5$ * 1≦K≦$b_1$+...+$b_n$ * 所有输入值都是整数。 ------------ 题目翻译者UID：370640

[problemUrl]: https://atcoder.jp/contests/abc061/tasks/abc061_c 空の配列が $ 1 $ つあります。 この配列に、整数を配列に挿入する操作を $ N $ 回行います。 $ i(1≦i≦N) $ 回目の操作では、配列に整数 $ a_i $ を $ b_i $ 個挿入します。 $ N $ 回の挿入操作後の配列の中で、$ K $ 番目に小さい数を求めてください。 例えば、配列が $ \{1,2,2,3,3,3\} $ の時、$ 4 $ 番目に小さい数は $ 3 $ となります。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ K $ $ a_1 $ $ b_1 $ $ : $ $ a_N $ $ b_N $

$ N $ 回の挿入操作後の配列の中で、$ K $ 番目に小さい数を出力せよ。

3 4
1 1
2 2
3 3

3

10 500000
1 100000
1 100000
1 100000
1 100000
1 100000
100000 100000
100000 100000
100000 100000
100000 100000
100000 100000

1

### 制約 - $ 1≦N≦10^5 $ - $ 1≦a_i,b_i≦10^5 $ - $ 1≦K≦b_1…+…b_n $ - 入力は全て整数である。 ### Sample Explanation 1 操作後の配列は、問題文に書かれている例と同じです。