Coin

A currency is issued in $N$ coin denominations. Denomination $i$ has a value of $v_i$ cents and a weight of $w_i$ grams ($1 \le i \le N$). Two denominations can share the same value or the same weight, but not both.

You are given $V$ and $W$. Find $M$, the smallest number of coins whose values add up to exactly $V$ cents and whose weights add up to exactly $W$ grams. If no such collection of coins exists, $M$ is $0$. Every denomination has an unlimited supply of coins.

The first line contains the number of denominations $N$, the target value $V$, and the target weight $W$, separated by spaces.

Each of the next $N$ lines contains the value $v_i$ and the weight $w_i$ of one denomination, separated by a space.

$1 \le N \le 20$, $1 \le V \le 150$, $1 \le W \le 150$, $1 \le v_i \le 150$, $1 \le w_i \le 150$.

Print $M$ on a single line. Print $0$ when no collection of coins reaches both totals.