配点 : $400$ 点

問題文

$N$ 種類の弁当が、それぞれ $1$ 個ずつ売られています。 $i = 1, 2, \ldots, N$ について、$i$ 種類目の弁当には $A_i$ 個のたこ焼きと $B_i$ 個のたい焼きが入っています。

高橋君は、 $X$ 個以上のたこ焼きと $Y$ 個以上のたい焼きを食べたいです。 高橋君がいくつかの弁当を選んで買うことで、 $X$ 個以上のたこ焼きと $Y$ 個以上のたい焼きを手に入れることが可能かどうか判定して下さい。また、可能な場合はそのために高橋君が購入しなければならない弁当の個数の最小値を求めて下さい。

各種類の弁当は $1$ 個しか売られていないため、同じ種類の弁当を $2$ 個以上購入することは出来ないことに注意して下さい。

制約

• $1 \leq N \leq 300$
• $1 \leq X, Y \leq 300$
• $1 \leq A_i, B_i \leq 300$
• 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

$N$

$X$ $Y$

$A_1$ $B_1$

$A_2$ $B_2$

$\vdots$

$A_N$ $B_N$

出力

高橋君が $X$ 個以上のたこ焼きと $Y$ 個以上のたい焼きを手に入れることが不可能な場合は $-1$ を出力し、 可能な場合はそのために高橋君が購入しなければならない弁当の個数の最小値を出力せよ。

3
5 6
2 1
3 4
2 3

2

高橋君は、$5$ 個以上のたこ焼きと $6$ 個以上のたい焼きを食べたいです。 高橋君は $2$ 種類目の弁当と $3$ 種類目の弁当を買うことで、 たこ焼きを $3 + 2 = 5$ 個、たい焼きを $4 + 3 = 7$ 個手に入れることができます。

3
8 8
3 4
2 3
2 1

-1

高橋君がたとえすべての弁当を買ったとしても、高橋君は $8$ 個以上のたこ焼きと $8$ 個以上のたい焼きを手に入れることが出来ません。 よって、$-1$ を出力します。