Problem Description
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), bi copies of an integer ai 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.
Input
The first line of the input will contain 2 integers, N and K.
Then N lines with 2 integers will follow, the i-th line will contain 2 integers, ai and bi.
Output
Print the K-th smallest integer in the array after the N operations.
Limits
- 1≤N≤105
- 1≤ai,bi≤105
- 1≤K≤b1…+…bn
- All input values are integers.
Subtask 1 (31%): bi = 1.
Subtask 2 (69%): No additional constraints.
Subtask 3 (0%): Sample test cases.
Sample Input 1
3 4
1 1
2 2
3 3
Sample Output 1
3
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