<PREV Problem:
NEXT>
Solved by 956 users: ...
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 

Athletes

Time limit = 3 second(s)

Every athlete is characterized by his mass mi (in kg) and strength si(in kg).

You are to find the maximum number of athletes that can form a tower standing one upon another.

An athlete can hold a tower of athlets with total mass equal to his strength or less than his strength.

Input contains the number of athletes n and their parameters:

n
m1 s1
m2 s2
...
mn  sn

If mi > mj then si > sj, but athletes with equal masses can be of different strength.

Number of athletes n < 100000. Masses and strengths are positive integers less than 2000000.

Input#1
4
3 4
2 2
7 6
4 5
Output#1
3

Author:

<PREV | Problem set | Search related messages | NEXT>


© acm.mipt DevGroup
The page was generated in 180ms

SW soft NIX
ID = 54.80.60.91