102193: [AtCoder]ABC219 D - Strange Lunchbox

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$.

问题描述

一家商店出售$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$。