C. Constructor
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

The well-known manufacturer of children's construction sets, OLEG, is going through some tough times. For reasons yet to be determined, all factories producing the parts for the sets have stopped. While the situation with the factories is being clarified, the company's management needs to release a new batch of sets, which will have to be assembled from the currently available parts.

There are $$$n$$$ types of construction parts. For each type $$$i$$$, the mass $$$m_i$$$ and the count $$$c_i$$$ of the parts are known. The management wants to assemble as many identical sets as possible, such that the total mass of the parts included in each set is at least $$$m_{\min}$$$ and at most $$$m_{\max}$$$. Two sets are considered identical if the number of parts of each type included in both sets is the same.

Determine the maximum number of sets that can be produced.

Input

The first line contains the integers $$$n$$$, $$$m_{\min}$$$, and $$$m_{\max}$$$ ($$$1 \le n \le 50$$$, $$$1 \le m_{\min} \le m_{\max} \le 10^4$$$). The next $$$n$$$ lines contain numbers $$$m_i$$$ and $$$c_i$$$ for each type $$$i$$$ ($$$1 \le m_i \le 10^4$$$, $$$1 \le c_i \le 10^6$$$, $$$1 \le i \le n$$$).

Output

Output a single integer — the maximum number of sets that can be produced.

Example
Input
3 12 13
3 8
4 6
7 9
Output
4
Note

In the example, one possible set can be constructed by taking two parts of type $$$1$$$ and one part of type $$$3$$$. The total mass of the set would be $$$3 + 3 + 7 = 13$$$, and from the available parts, a total of $$$4$$$ such sets can be assembled.