Problem Statement

There are $N$ building blocks. The $i$-th block has weight $w_i$ and hardness $s_i$.

Consider choosing one or more blocks and stacking them so that the following condition is satisfied. Find the maximum number of blocks that can be stacked.

Condition

For every stacked block (call it block P), the total weight of the blocks above block P (not including block P) is at most the hardness of block P.

More Formal Problem Statement

You are given an integer $N$. You are also given $N$ integers $w_1, w_2,…, w_N$ and $N$ integers $s_1, s_2,…, s_N$.

Consider constructing a non-empty integer sequence $A$ that satisfies the following condition. Find the maximum possible number of elements of $A$.

Condition

• (The number of elements may be any number. For convenience, let it be denoted by $X$ here.)
• For all $i$ satisfying $1 \leq i \leq X$, $1 \leq A_i \leq N$
• For all ($i, j$) satisfying $1 \leq i,j \leq X$ and $i \neq j$, $A_i \neq A_j$
• For all $i$ satisfying $1 \leq i \leq X$, $\displaystyle \sum_{k=1}^{i - 1} w_{A_k} \leqq s_{A_i}$

Input

$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$
• All input values are integers

Output

Output the value you found, followed by a newline.

Sample

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