题目描述

小 D 的计算机存储空间有限，他将一个长数列用压缩方式存储：记录每种数值出现了多少次，而不是逐个记录每个数。

具体来说，压缩记录由 $N$ 行描述，每行两个整数 $a_i$ 和 $b_i$，表示数值 $a_i$ 出现了 $b_i$ 次。

现在，小 D 想知道：如果将压缩记录还原为完整数列并从小到大排序，第 $K$ 小的数是多少？

输入格式

输入共 $N + 1$ 行。

第一行，两个整数 $N$ 和 $K$，分别表示压缩记录的行数和需要查找的第 $K$ 小。

接下来 $N$ 行，每行两个整数 $a_i$ 和 $b_i$，表示数值 $a_i$ 出现了 $b_i$ 次。

输出格式

输出共一行，包含一个整数，表示第 $K$ 小的数值。

3 4
1 3
2 2
3 3

2

2 5
10 3
20 2

20

4 1
5 100
2 50
8 30
1 10

1

样例解释

对于样例 1：还原数列 $[1,1,1,2,2,3,3,3]$ 已有序，第 $4$ 小为 $2$。

对于样例 2：还原数列 $[10,10,10,20,20]$，第 $5$ 小为 $20$。

对于样例 3：输入不按顺序（$5,2,8,1$），排序后数值从小到大依次为 $1,2,5,8$，$1$ 出现 $10$ 次，第 $1$ 小即为 $1$。

数据规模与约定

对于 $100\%$ 的数据，$1 \le N \le 10^5$，$1 \le a_i, b_i \le 10^9$，$1 \le K \le 10^9$，$K$ 不超过总元素数。