시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 256 MB | 216 | 63 | 32 | 25.397% |
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.
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.
300 1000 1000 1200 200 600 100 101
3