<PREV Problem:
NEXT>
Solved by 963 users: ...
UserDateAttemptTimeCMSC
white_dragon09 jan 2010Perl6301.5721 
white_dragon09 jan 2010Perl2301.4826 
white_dragon09 jan 2010Perl1501.2032 
white_dragon09 jan 2010Perl1401.1938 
xtender08 jan 2010Perl2001.2048 
kil11 jul 2007Ruby2503.0150 
vi00211 jul 2007Ruby2202.9851 
var11 jul 2007Ruby1403.0851 
var11 jul 2007Ruby1302.9453 
kil11 jul 2007Ruby1603.0154 
sb3ar11 may 2008Ruby1703.2155 
sb3ar12 feb 2008Ruby1503.2156 
kil11 jul 2007Ruby2403.0057 
sb3ar11 may 2008Ruby1603.0358 
s9730229 jan 2010Ruby802.6660 
s9730229 jan 2010Ruby402.5761 
s9730229 jan 2010Ruby302.4962 
qdiesel07 nov 2008Ruby303.0663 
bush25 feb 2013Ruby202.1967 
stasg710 dec 2009Ruby1302.0768 
Languages
C++
622
C
211
FPC
58
Java
42
Python
18
Kylix
15
Ruby
15
Perl
5
Lua
3
Scheme
1
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 

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 190ms

SW soft NIX
ID = 3.81.28.10