Pro Gamer Youngsik

Youngsik is a professional player of ShomCraft. Before his unavoidable match against his rival Minsik, he wants to produce as many of the strongest units as possible within the remaining time.

ShomCraft has units numbered from 1 to N. The game starts with exactly one unit of type 1. There are no buildings, so units produce the next numbered unit: a unit of type i can produce one unit of type i+1. This production takes Time[i] seconds and consumes Cost[i] resources. A unit that starts production can produce again after that production finishes, and different units can produce simultaneously.

A unit with a larger number defeats every unit with a smaller number. Therefore, Youngsik wants to create as many units of type N as possible before the fight begins. Given the remaining time T and the current amount of resources C, compute the maximum number of type N units he can produce. Resources never increase, and issuing commands takes 0 seconds.

The first line contains the number of unit types N. N is a positive integer not greater than 300.

The second line contains the current resources C and the remaining time T. C and T are positive integers not greater than 300.

Each of the next N-1 lines contains Cost[i] and Time[i] in order. The i-th of these lines gives the resources and time needed for a unit of type i to produce a unit of type i+1.

Print the maximum number of type N units that can be produced.