100612: [AtCoder]ABC061 C - Big Array
Memory Limit：256 MB
Time Limit：2 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
Score : $300$ points
Problem Statement
There is an empty array. The following $N$ operations will be performed to insert integers into the array. In the $i$-th operation $(1≤i≤N)$, $b_i$ copies of an integer $a_i$ are inserted into the array. Find the $K$-th smallest integer in the array after the $N$ operations. For example, the $4$-th smallest integer in the array $\{1,2,2,3,3,3\}$ is $3$.
Constraints
- $1≤N≤10^5$
- $1≤a_i,b_i≤10^5$
- $1≤K≤b_1…+…b_n$
- All input values are integers.
Input
Input is given from Standard Input in the following format:
$N$ $K$ $a_1$ $b_1$ $:$ $a_N$ $b_N$
Output
Print the $K$-th smallest integer in the array after the $N$ operations.
Sample Input 1
3 4 1 1 2 2 3 3
Sample Output 1
3
The resulting array is the same as the one in the problem statement.
Sample Input 2
10 500000 1 100000 1 100000 1 100000 1 100000 1 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000
Sample Output 2
1