AT_cf17_final_d.Zabuton

某一年份的 CODE FESTIVAL 本赛聚集了 $N$ 名参赛者。参赛者 $i$ 的身高为 $H_i$，力量为 $P_i$。

Ringo 想让参赛者们进行一个堆“座布团”的游戏。

参赛者可以按照自己喜欢的顺序排队，轮到某个人时，他们会在一个地方堆“座布团”。最开始没有任何“座布团”。当轮到参赛者 $i$ 时，如果已经堆积的“座布团”数量不超过 $H_i$，他就会正好堆 $P_i$ 个“座布团”；否则，他会放弃，不堆任何“座布团”。

Ringo 希望尽可能让更多的参赛者参与堆“座布团”。通过巧妙安排参赛者的顺序，最多能有多少名参赛者参与堆“座布团”呢？

输入以如下格式从标准输入读入。

$N$ $H_1$ $P_1$ $H_2$ $P_2$ $\ldots$ $H_N$ $P_N$

输出能够参与堆“座布团”的参赛者人数的最大值。

限制条件

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

样例解释 1

如果按输入顺序排列参赛者，第 $1$、$3$ 位参赛者可以堆“座布团”。同时，不存在可以让 $3$ 位参赛者全部参与的顺序，因此答案是 $2$。

样例解释 2

如果按第 $2$ 位、第 $3$ 位、第 $1$ 位参赛者的顺序排列，则所有人都可以堆“座布团”。

由 ChatGPT 5 翻译