← 返回题目列表

Codeforces · 725/D

D. 竞赛气球

中文机器翻译题面 查看原题

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 队平等)。