시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 81 20 13 20.968%

문제

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

힌트