分数: 400 点
问题陈述
某商店有卖 N 多种饭盒,每种一个。
对于每个 i = 1, 2, \ldots, N, i第一种饭盒包含 A_i 章鱼烧(章鱼丸)和 B_i 鲷鱼烧(鱼形蛋糕)。
高桥想吃东西 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
就算他把所有的饭盒都买了,也不可能得到至少
WAtCoder 上的 8 章鱼烧和至少 8 鲷鱼烧。
因此,打印 -1.