Strange Lunchbox

题目描述

一家商店出售 $N$ 种便当，每种各有一份。
对于每个 $i = 1, 2, \ldots, N$，第 $i$ 种便当包含 $A_i$ 个章鱼烧（takoyaki）和 $B_i$ 个鲷鱼烧（taiyaki）。 高桥想吃至少 $X$ 个章鱼烧和至少 $Y$ 个鲷鱼烧。
判断是否可以通过购买若干便当获得至少 $X$ 个章鱼烧和至少 $Y$ 个鲷鱼烧。如果可以，找出高桥为达到该目标必须购买的最少便当数。 注意每种便当仅有一份库存；不能购买同一种便当两份或更多。

输入格式

输入按照下列格式自标准输入给出： $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

3
8 8
3 4
2 3
2 1

-1

提示

$1 \leq N \leq 300$ $1 \leq X, Y \leq 300$ $1 \leq A_i, B_i \leq 300$ 输入中的所有数值均为整数。他想吃至少 $5$ 个章鱼烧和至少 $6$ 个鲷鱼烧。
购买第 2 和第 3 个便当可以得到 $3 + 2 = 5$ 个章鱼烧和 $4 + 3 = 7$ 个鲷鱼烧。
即使购买所有便当，也无法得到至少 $8$ 个章鱼烧和至少 $8$ 个鲷鱼烧。
因此，输出 $-1$。

标签: AtCoder|abc219D

来源

AtCoder|abc219D