Chèn dãy
Ban đầu, cho 1 dãy rỗng. Thực hiện thao tác sau $N$ lần để chèn các số nguyên vào dãy. Ở thao tác thứ $i(1 \le i \le N)$, số nguyên $a_i$ sẽ được chèn vào dãy $b_i$ lần.
Hãy tìm phần tử nhỏ thứ $K$ của dãy số sau khi thực hiện $N$ thao tác.
Dữ liệu
- Dòng đầu chứa 2 số nguyên $N$ và $K (1 \le N \le 10^5; 1 \le K \le b_1+b_2+...+b_N)$;
- $N$ dòng tiếp theo, dòng thứ $i$ chứa 2 số nguyên $a_i$ và $b_i (1 \le a_i,b_i \le 10^5)$
Kết quả
- In ra phần tử nhỏ thứ $K$ của dãy sau $N$ thao tác.
Ví dụ
Ví dụ 1
input
3 4
1 1
2 2
3 3
output
3
Comments