Matryoshka Dolls

A matryoshka is a Russian doll that holds another doll inside it. Every doll has its own weight and its own storage ability.

A doll holds at most one other doll directly, and that doll holds the next one, so the dolls form a single chain. The storage ability includes the doll's own weight. For every doll in the chain, its own weight plus the weight of all dolls nested inside it must be at most its storage ability. A doll that weighs 400g and has a storage ability of 900g carries at most 500g of dolls inside it.

Pick dolls from the given set and nest them into one chain. Report how many dolls the longest such chain holds.

Each line holds the weight and the storage ability of one doll, separated by one or more spaces. Both values are in grams. The input runs to the end of the file and describes at most 6000 dolls. A weight is a positive integer at most 100000, and a storage ability is a positive integer at most 20000000.

Print one integer on a single line, the largest number of dolls that can be nested in one chain without exceeding the storage ability of any doll.