102193: [AtCoder]ABC219 D - Strange Lunchbox
Description
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$.
Input
题意翻译
有 $n$ 份套餐，每份套餐都有两个价值 $a_i$ 和 $b_i$。我们称一个选择方法是合法的，仅当选择的所有套餐的 $\sum a_i\ge x$，$\sum b_i\ge y$，每份套餐只能选择一次。 输入第一行是一个整数 $n$，第二行是两个整数 $x$ 和 $y$，接下来的 $n$ 行每行两个整数 $a_i$ 和 $b_i$。 如果不存在合法的选择方法输出 ```-1```，否则输出在所有合法的选择方案中最少需要购买的套餐份数。 输入中的所有数均为值在 $[1,300]$ 之间的整数。Output
得分：$400$分
问题描述
一家商店出售$N$种午餐盒，每种一个。
对于每个$i = 1, 2, \ldots, N$，第$i$种午餐盒包含$A_i$个章鱼小丸子（takoyaki）和$B_i$个鱼形蛋糕（taiyaki）。
高桥想要吃$X$个或更多的章鱼小丸子和$Y$个或更多的鱼形蛋糕。
确定是否有可能购买一定数量的午餐盒以获得至少$X$个章鱼小丸子和至少$Y$个鱼形蛋糕。如果可能，找出高桥必须购买的最少午餐盒数量以获得它们。
注意每种午餐盒只有一件库存；你不能购买同一种午餐盒两个或更多个。
限制条件
- $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$个或更多的鱼形蛋糕。
购买第二个和第三个午餐盒将使他获得$3 + 2 = 5$个鱼形蛋糕和$4 + 3 = 7$个章鱼小丸子。
样例输入 2
3 8 8 3 4 2 3 2 1
样例输出 2
-1
即使他要购买所有午餐盒，也很难获得至少$8$个章鱼小丸子和至少$8$个鱼形蛋糕。
因此，打印$-1$。