Problem D: Matryoshka Dolls
Problem Description
You most likely have seen the Russian Dolls which stack inside each other.
For example:
Each doll has a different weight and storage ability.
Your task is to nest as many dolls as possible.
Input Specification
Standard input consists of several lines, each containing a pair of integers
separated by one or more space characters, specifying the weight and
storage ability
of a doll.
The weight of the doll is in grams.
The storage ability, also in grams, is the doll's overall storage capacity,
including its own weight.
That is, a doll weighing 400g with a strength of 900g could carry 500g of
dolls inside it.
There are at most 6000 dolls. The maximum weight of any doll
is 100000g and the maximum storage capacity is 20000000g.
Your output is a single integer indicating the maximum number of dolls
that can be nested without exceeding the storage ability of any one.
Sample Input
300 1000
1000 1200
200 600
100 101
Output for Sample Input
3