102193: [AtCoder]ABC219 D - Strange Lunchbox

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:1 Solved:0

Description

Score : $400$ points

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

Input

题意翻译

有 $n$ 份套餐,每份套餐都有两个价值 $a_i$ 和 $b_i$。我们称一个选择方法是合法的,仅当选择的所有套餐的 $\sum a_i\ge x$,$\sum b_i\ge y$,每份套餐只能选择一次。 输入第一行是一个整数 $n$,第二行是两个整数 $x$ 和 $y$,接下来的 $n$ 行每行两个整数 $a_i$ 和 $b_i$。 如果不存在合法的选择方法输出 ```-1```,否则输出在所有合法的选择方案中最少需要购买的套餐份数。 输入中的所有数均为值在 $[1,300]$ 之间的整数。

Output

得分:$400$分

问题描述

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

加入题单

上一题 下一题 算法标签: