問題文

$N$ 個の積み木があります。$i$ 個目の積み木の重さは $w_i$ で、硬さは $s_i$ です。

以下の条件を満たすように、1 個以上の積み木を選んでそれらを積み上げることを考えます。最大で何個の積み木を積み上げられるかを求めてください。

条件

積み上げた全ての積み木それぞれ (積み木 P とする) において、積み木 P より上にある積み木 (積み木 P を含まない) の重さの合計が、積み木 P の硬さ以下である。

より厳密な問題文

整数 $N$ が与えられます。また、$N$ 個の整数 $w_1, w_2,…, w_N$ と、$N$ 個の整数 $s_1, s_2,…, s_N$ が与えられます。

以下の条件を満たすように、空でない整数列 $A$ を作ることを考えます。考えられる $A$ の要素数で最大のものを求めてください。

条件

• (要素数はいくつでもよい。便宜上、ここでは要素数を $X$ としておく。)
• $1 \leq i \leq X$ を満たす全ての $i$ において、$1 \leq A_i \leq N$
• $1 \leq i,j \leq X$ かつ $i \neq j$ を満たす全ての ($i, j$) において、$A_i \neq A_j$
• $1 \leq i \leq X$ を満たす全ての $i$ において、$\displaystyle \sum_{k=1}^{i - 1} w_{A_k} \leqq s_{A_i}$

入力

$N$
$w_1\ \ s_1$
$w_2\ \ s_2$
$:$
$w_N\ \ s_N$

• $1 \leq N \leq 10^3$
• $1 \leq w_i, s_i \leq 10^9$
• 入力はすべて整数である

出力

求めた値を出力し、最後に改行せよ。

サンプル

3
1 3
4 2
5 2

2

8
23907824 512
347613 276
29074 981
409801 837
2939123 285
1087432 18
1238930 9832
287931 23

1

20
702942310 384194029
229351257 240012589
888749549 277038040
894642151 627015876
807346218 681631935
635995728 25027850
25753102 594612993
59739707 245417032
643586787 827447411
578510634 515373169
749153251 734083014
280524008 353961256
293345690 296823276
543870074 113249829
427006969 902166637
885344786 189584191
207361148 780822106
547181796 158349222
741195942 95500093
820886476 460559617

6