AT_abc219_d [ABC219D] Strange Lunchbox

题目描述

有 $N$ 种便当，每种便当各有 $1$ 个在售。
对于 $i=1,2,\ldots,N$，第 $i$ 种便当中包含 $A_i$ 个章鱼烧和 $B_i$ 个鲷鱼烧。

高桥君希望吃到至少 $X$ 个章鱼烧和至少 $Y$ 个鲷鱼烧。
请判断高桥君是否可以通过购买若干个便当，使得章鱼烧不少于 $X$ 个且鲷鱼烧不少于 $Y$ 个。如果可以，请求出高桥君需要购买的便当最少数量。

注意，每种便当只有 $1$ 个，不能购买同一种便当超过一次。

输入格式

输入按以下格式从标准输入读入。

$N$ $X$ $Y$
$A_1$ $B_1$
$A_2$ $B_2$
$\vdots$
$A_N$ $B_N$

输出格式

如果高桥君无法获得至少 $X$ 个章鱼烧和至少 $Y$ 个鲷鱼烧，则输出 $-1$。
如果可以，请输出高桥君需要购买的便当的最小数量。

输入输出样例 #1

输入 #1

3
5 6
2 1
3 4
2 3

输出 #1

2

输入输出样例 #2

输入 #2

3
8 8
3 4
2 3
2 1

输出 #2

-1

说明/提示

限制条件

• $1 \leq N \leq 300$
• $1 \leq X, Y \leq 300$
• $1 \leq A_i, B_i \leq 300$
• 所有输入均为整数。

样例解释 1

高桥君希望吃到至少 $5$ 个章鱼烧和至少 $6$ 个鲷鱼烧。
高桥君可以购买第 $2$ 种和第 $3$ 种便当，这样可以获得 $3+2=5$ 个章鱼烧和 $4+3=7$ 个鲷鱼烧。

样例解释 2

即使高桥君买下所有便当，也无法获得至少 $8$ 个章鱼烧和 $8$ 个鲷鱼烧。因此，输出 $-1$。

由 ChatGPT 4.1 翻译