题目内容

运维侧汇总评估得到 $N$ 条告警记录。第 $j$ 条记录有两个整型字段：级别 $h_j$ 与占用额度 $c_j$。值班同学要选定一个非负整数门槛 $T$，只处理级别不低于该门槛的告警，且这些告警的额度之和不得超过预算 $L$。

对门槛 $T$，纳入集合为所有满足 $h_j\ge T$ 的记录，其额度总和为

其中 $j_1,j_2,\ldots,j_s$ 是全部满足 $h_j\ge T$ 的下标；若没有这样的记录，则 $U(T)=0$。

$T$ 合法当且仅当 $U(T)\le L$。在所有合法门槛中，求最小的非负整数 $T$。

取 $T$ 大于所有级别时纳入为空，$U=0$，因此合法门槛一定存在。若 $T=0$ 已合法，答案为 $0$。

输入描述

第一行两个整数 $N,L$，表示告警条数与额度预算。

接下来 $N$ 行，每行两个整数 $h_j,c_j$，表示第 $j$ 条告警的级别与占用额度。

输出描述

输出一个整数，表示最小合法门槛 $T$。

样例1

输入

3 6
4 2
7 5
1 3

输出

5

说明

• $T=4$：纳入级别 $4,7$，额度 $2+5=7>6$，不合法。
• $T=5$：只纳入级别 $7$，额度 $5\le 6$，合法。
• $T=0$ 会纳入全部，额度 $10>6$。最小合法门槛为 $5$。

数据范围

• $1\le N\le 100000$
• $0\le L\le 1\times 10^{18}$
• $0\le h_j\le 1000000000$
• $0\le c_j\le 1000000000$
• 所有输入均为整数