← 返回题目列表

AtCoder · cf17_final_d

D. 扎布顿

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

分数: 700 点

问题陈述

某年Code FESTIVAL决赛中,有 N 参与者。 的 高度 和 电源 咒语的 参加者人数 i is H_i 和 P_i。

Ringo 正在主持一场堆叠 zabuton(垫子)的游戏。

参与者将按某种顺序排成一排,然后他们将依次尝试将 zabuton 添加到 zabuton 堆栈中。 最初,堆栈是空的。 当它是参与者时 轮到 i,如果有 H_i 或更少的 zabuton 已经堆叠,他/她将准确添加 P_i zabuton 到堆栈。否则,他/她就会放弃,什么也不做。

Ringo 希望最大化可以将 zabuton 添加到堆栈的参与者数量。 有多少参与者可以按照参与者的最佳顺序将 zabuton 添加到堆栈中?

约束

  • 1 \leq N \leq 5000
  • 0 \leq H_i \leq 10^9
  • 1 \leq P_i \leq 10^9

输入

输入由标准输入按以下格式给出:

N
H_1 P_1
H_2 P_2
:
H_N P_N

输出

打印可以将 zabuton 添加到堆栈的最大参与者数量。


示例输入 1

3
0 2
1 3
3 4

示例输出 1

2

当参与者按照输入的顺序排队时,参与者 1 和 3 将能够添加zabuton。

另一方面,没有命令让所有三个参与者都可以添加 zabuton。因此,答案是 2.


示例输入 2

3
2 4
3 1
4 1

示例输出 2

3

当参与者按顺序排队时 2, 3, 1,他们都可以添加zabuton。


示例输入 3

10
1 3
8 4
8 3
9 1
6 4
2 3
4 2
9 2
8 3
0 1

示例输出 3

5