← 返回题目列表

AtCoder · abc219_d

G. 奇怪的饭盒

中文机器翻译题面 查看原题

分数: 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.