← 返回题目列表

AtCoder · utpc2011_5

E. 首次验收

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

对于编程竞赛中的每个问题, 第一个正确回答问题的人的姓名和时间。 在解释中通常将其称为首次接受(第一个正确答案)。

虽然我已经有一段时间第一次参加编程比赛了,但我不知道自己会在预赛中失败。 所以,一开始,与其追求稍微高一点的分数, 获得更多的第一认可并让大家知道你的存在不是更好吗?

如果你使用你的能力,当你看到每个问题的那一刻, 多少分钟可以解决这个问题? 您可以看到问题开始后多少分钟,该问题将由除您之外的参与者首先解决。

使用此信息, 让我们创建一个程序来计算可以获得多少首次接受。

問題

N 考虑一个由问题组成的编程竞赛。 问题 如何自己解决 i 需要 Ai 秒, 还有,问题 i 启动后 假设除您之外的其他参与者在 Bi 秒内首先解决了该问题。

你可以自由决定解决问题的顺序,但是 一旦你开始解决一个问题,你就会继续解决它,直到解决它为止。 当你解决完一个问题并开始下一个问题时,等等。 除了解决问题所花费的时间之外的时间被认为足够小并且将被忽略。 另外,假设在会议结束时所有问题都将由除您之外的一名或多名参与者解决。

比您以外的参与者首先解决的速度更快, 或者同时出现问题 当你求解 i 时, 问题 您可以获得 i 的首次接受。 也就是说,问题 开始后 i 假设求解在 ti 秒内完成, ti ≤ Bi 那么问题来了 您可以获得 i 的首次接受。

编写一个程序来计算可以获得首次验收的最大问题数。

入力

第一行输入是单个整数 包含 N 。

继续 N 行提供有关每个问题的信息。 这些行中 i 行有两个数字 Ai, Bi 被书写。

出力

打印可以获得的最大首次接受数。

制約

  • 1 ≤ N ≤ 1000
  • 1 ≤ Ai ≤ 106 (1 ≤ i ≤ N)
  • 1 ≤ Bi ≤ 106 (1 ≤ i ≤ N)

部分点

针对该问题的判断设置了一组20分的测试用例。 该组中包含的测试用例的输入满足以下条件。

  • 1 ≤ N ≤ 16

入出力例

入出力例 1

入力例 1:

3
3 5
5 9
10 20

输入示例 1 的输出示例:

3

入出力例 2

入力例 2:

3
3 2
5 15
10 12

输入示例 2 的输出示例:

2