ACM-ICPC 竞赛的一个传统是,团队每解决一个问题就会获得一个气球。我们假设提交时间并不重要,并且团队仅根据他们拥有的气球数量进行排序。这意味着一个人的名次等于拥有更多气球的队伍的数量加1。例如,如果有七支队伍拥有更多的气球,你将获得第八名。允许有领带。
你应该知道比赛前吃东西很重要。如果一个团队的气球数量大于该团队的重量,则该团队开始与他们的工作站一起漂浮在空中。他们最终触及了天花板,这是规则严格禁止的。该球队随后将被取消资格,并且不会出现在积分榜上。
一场比赛刚刚结束。有n支球队,编号为1到n。第 i 队有 ti 气球和重量 wi。可以保证 ti 不会超过 wi,因此最初没有人漂浮。
Limak 是一线队的成员。他不喜欢作弊,也绝不会偷其他球队的气球。相反,他可以把他的气球送给其他团队,可能会让它们漂浮起来。利马克可以赠送他团队中的零个或多个气球。显然,他不能赠送比他的团队最初拥有的更多的气球。
Limak 最好的地方是什么?
输入
标准输入的第一行包含一个整数 n (2 ≤ n ≤ 300 000) — 球队数量。
接下来的 n 行中的第 i 行包含两个整数 ti 和 wi (0 ≤ ti ≤ wi ≤ 1018)——分别是气球的数量和第 i 队的重量。利马克是一线队的成员。
输出
打印一个整数,表示 Limak 可以获得的最佳位置。
示例
输入 #1
8 20 1000 32 37 40 1000 45 50 16 16 16 16 14 1000 2 1000
输出 #1
3
输入 #2
7 4 4 4 4 4 4 4 4 4 4 4 4 5 5
输出 #2
2
输入 #3
7 14000000003 1000000000000000000 81000000000 88000000000 5000000000 7000000000 15000000000 39000000000 46000000000 51000000000 0 1000000000 0 0
输出 #3
2
注意
在第一个示例中,Limak 最初有 20 个气球。有三队拥有更多气球(32、40 和 45 个气球),因此利马克最初获得第四名。一种最佳策略是:
1. Limak 向拥有 32 个气球、重量为 37 的团队赠送了 6 个气球,刚好足以让他们飞起来。不幸的是,利马克现在只有 14 个气球,他将获得第五名。
2. Limak 向拥有 45 个气球的团队赠送 6 个气球。现在他们有 51 个气球,重量为 50,因此他们飞行并被取消资格。
3. Limak 向最初有 16 个气球的两队各提供 1 个气球。
4. Limak 有 20 - 6 - 6 - 1 - 1 = 6 个气球。
5. 还剩下三队,他们的气球数量分别是 40、14 和 2。
6. Limak 获得第三名,因为有两队拥有更多气球。
在第二个样本中,Limak 排名第二,并且无法提高。
在第三个样本中,Limak 的气球刚好足以摆脱第 2、3 和 5 队(分别拥有 81 000 000 000、5 000 000 000 和 46 000 000 000 个气球的队伍)。剩下零个气球,他将获得第二名(与第 6 队和第 7 队平等)。