题目描述

有一个数组 $S$，一开始是空的。接下来对这个数组进行 $N$ 次插入操作。

第 $i$ 次操作会向数组中加入 $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$ 小的数。

3 4
1 1
2 2
3 3

3

4 200000
1 100000
1 100000
100000 100000
100000 100000

1

输入样例 #3

1 1
1 1

输出样例 #3

1

数据范围

对于 $50\%$ 数据：$1\le N,a_i,b_i\le 10^5$。

对于 $100\%$ 数据：$1\le N\le 10^5$，$1\le a_i,b_i\le 10^9$，$1\le K\le b_1+b_2+\cdots+b_N$。