/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 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 を出力し、 可能な場合はそのために高橋君が購入しなければならない弁当の個数の最小値を出力せよ。
入力例 1
3 5 6 2 1 3 4 2 3
出力例 1
2
高橋君は、5 個以上のたこ焼きと 6 個以上のたい焼きを食べたいです。
高橋君は 2 種類目の弁当と 3 種類目の弁当を買うことで、
たこ焼きを 3 + 2 = 5 個、たい焼きを 4 + 3 = 7 個手に入れることができます。
入力例 2
3 8 8 3 4 2 3 2 1
出力例 2
-1
高橋君がたとえすべての弁当を買ったとしても、高橋君は 8 個以上のたこ焼きと 8 個以上のたい焼きを手に入れることが出来ません。
よって、-1 を出力します。
Score : 400 points
Problem Statement
A shop sells N kinds of lunchboxes, one for each kind.
For each i = 1, 2, \ldots, N, the i-th kind of lunchbox contains A_i takoyaki (octopus balls) and B_i taiyaki (fish-shaped cakes).
Takahashi wants to eat X or more takoyaki and Y or more taiyaki.
Determine whether it is possible to buy some number of lunchboxes to get at least X takoyaki and at least Y taiyaki. If it is possible, find the minimum number of lunchboxes that Takahashi must buy to get them.
Note that just one lunchbox is in stock for each kind; you cannot buy two or more lunchboxes of the same kind.
Constraints
- 1 \leq N \leq 300
- 1 \leq X, Y \leq 300
- 1 \leq A_i, B_i \leq 300
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N X Y A_1 B_1 A_2 B_2 \vdots A_N B_N
Output
If Takahashi cannot get at least X takoyaki and at least Y taiyaki, print -1; otherwise, print the minimum number of lunchboxes that he must buy to get them.
Sample Input 1
3 5 6 2 1 3 4 2 3
Sample Output 1
2
He wants to eat 5 or more takoyaki and 6 or more taiyaki.
Buying the second and third lunchboxes will get him 3 + 2 = 5 taiyaki and 4 + 3 = 7 taiyaki.
Sample Input 2
3 8 8 3 4 2 3 2 1
Sample Output 2
-1
Even if he is to buy every lunchbox, it is impossible to get at least 8 takoyaki and at least 8 taiyaki.
Thus, print -1.