G. Glasses of Solutions
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given $$$n$$$ glasses containing solutions of salt. For each solution, the total mass and the mass of the salt contained within it are known. The objective is to determine the number of non-empty subsets of these $$$n$$$ glasses such that if their contents are combined into an empty glass, the resulting solution will achieve a specified mass fraction of salt.

Input

The first line contains three integers $$$n$$$, $$$a$$$, and $$$b$$$ ($$$2 \leq n \leq 35$$$, $$$0 \leq a \leq 10\,000$$$, $$$\max(a, 1) \leq b \leq 10\,000$$$, $$$\text{gcd}(a, b) = 1$$$) — the number of glasses containing solutions, the numerator, and the denominator of the fraction $$$\frac{a}{b}$$$ representing the desired mass fraction of salt, respectively.

The following $$$n$$$ lines each contain two integers $$$m_i$$$ and $$$t_i$$$ ($$$0 \leq m_i \leq 10\,000$$$, $$$\max(m_i, 1) \leq t_i \leq 10\,000$$$) — the mass of salt and the total mass of the $$$i$$$-th solution ($$$i = 1, 2, \ldots, n$$$).

Output

Output a single integer – the number of ways to achieve a solution with a mass fraction of salt $$$\frac{a}{b}$$$.

Examples
Input
5 1 2
1 2
1 2
1 2
1 2
1 4
Output
15
Input
2 0 1
0 1
1 1
Output
1