分数: 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