A7074. Welcome24ever 和便当
编程题
普及/提高-
知识点
题目描述
有 $N$ 种便当,每种便当各有 $1$ 个在售。
对于 $i = 1,2,\dots,N$,第 $i$ 种便当中包含 $A_i$ 个章鱼烧和 $B_i$ 个鲷鱼烧。
Welcome24ever 希望吃到至少 $X$ 个章鱼烧,并且至少 $Y$ 个鲷鱼烧。
他可以从这 $N$ 种便当中选择若干个(每种最多选一次),请你判断是否存在一种选择方式,使得:
- 所有选中便当中的章鱼烧总数不少于 $X$;
- 所有选中便当中的鲷鱼烧总数不少于 $Y$。
如果存在,请你求出需要购买的便当最少数量;如果不存在,输出 $-1$。
对于 $i = 1,2,\dots,N$,第 $i$ 种便当中包含 $A_i$ 个章鱼烧和 $B_i$ 个鲷鱼烧。
Welcome24ever 希望吃到至少 $X$ 个章鱼烧,并且至少 $Y$ 个鲷鱼烧。
他可以从这 $N$ 种便当中选择若干个(每种最多选一次),请你判断是否存在一种选择方式,使得:
- 所有选中便当中的章鱼烧总数不少于 $X$;
- 所有选中便当中的鲷鱼烧总数不少于 $Y$。
如果存在,请你求出需要购买的便当最少数量;如果不存在,输出 $-1$。
输入格式
输入的第一行包含一个整数 $N$。
第二行包含两个整数 $X,Y$。
接下来的 $N$ 行中,第 $i$ 行包含两个整数 $A_i,B_i$,表示第 $i$ 种便当中章鱼烧和鲷鱼烧的数量。
第二行包含两个整数 $X,Y$。
接下来的 $N$ 行中,第 $i$ 行包含两个整数 $A_i,B_i$,表示第 $i$ 种便当中章鱼烧和鲷鱼烧的数量。
输出格式
如果无法通过购买若干个便当获得至少 $X$ 个章鱼烧和至少 $Y$ 个鲷鱼烧,则输出 $-1$。
否则,输出一个整数,表示需要购买的便当的最小数量。
否则,输出一个整数,表示需要购买的便当的最小数量。
输入输出样例
输入 #1
3 5 6 2 1 3 4 2 3
输出 #1
2
输入 #2
3 8 8 3 4 2 3 2 1
输出 #2
-1
说明/提示
## 数据范围
- $1 \le N \le 300$;
- $1 \le X \le 300$;
- $1 \le Y \le 300$;
- 对所有 $i$,有 $1 \le A_i \le 300$,$1 \le B_i \le 300$;
- 输入中的所有数都是整数。
### 样例解释 1
Welcome24ever 希望吃到至少 $5$ 个章鱼烧和至少 $6$ 个鲷鱼烧。
便当列表如下:
- 第 $1$ 种:$2$ 个章鱼烧,$1$ 个鲷鱼烧;
- 第 $2$ 种:$3$ 个章鱼烧,$4$ 个鲷鱼烧;
- 第 $3$ 种:$2$ 个章鱼烧,$3$ 个鲷鱼烧。
可以选择第 $2$ 种和第 $3$ 种便当,此时:
- 章鱼烧总数为 $3 + 2 = 5$;
- 鲷鱼烧总数为 $4 + 3 = 7$。
这已经满足“至少 $5$ 个章鱼烧、至少 $6$ 个鲷鱼烧”的要求,并且只买了 $2$ 个便当。
可以证明不存在只买 $1$ 个便当就能满足条件的方案,所以答案为 $2$。
### 样例解释 2
即使 Welcome24ever 买下所有 $3$ 个便当,总共也只有:
- 章鱼烧:$3 + 2 + 2 = 7$;
- 鲷鱼烧:$4 + 3 + 1 = 8$。
章鱼烧总数只有 $7$,小于需要的 $8$,无论如何选择都达不到要求,所以输出 $-1$。
- $1 \le N \le 300$;
- $1 \le X \le 300$;
- $1 \le Y \le 300$;
- 对所有 $i$,有 $1 \le A_i \le 300$,$1 \le B_i \le 300$;
- 输入中的所有数都是整数。
### 样例解释 1
Welcome24ever 希望吃到至少 $5$ 个章鱼烧和至少 $6$ 个鲷鱼烧。
便当列表如下:
- 第 $1$ 种:$2$ 个章鱼烧,$1$ 个鲷鱼烧;
- 第 $2$ 种:$3$ 个章鱼烧,$4$ 个鲷鱼烧;
- 第 $3$ 种:$2$ 个章鱼烧,$3$ 个鲷鱼烧。
可以选择第 $2$ 种和第 $3$ 种便当,此时:
- 章鱼烧总数为 $3 + 2 = 5$;
- 鲷鱼烧总数为 $4 + 3 = 7$。
这已经满足“至少 $5$ 个章鱼烧、至少 $6$ 个鲷鱼烧”的要求,并且只买了 $2$ 个便当。
可以证明不存在只买 $1$ 个便当就能满足条件的方案,所以答案为 $2$。
### 样例解释 2
即使 Welcome24ever 买下所有 $3$ 个便当,总共也只有:
- 章鱼烧:$3 + 2 + 2 = 7$;
- 鲷鱼烧:$4 + 3 + 1 = 8$。
章鱼烧总数只有 $7$,小于需要的 $8$,无论如何选择都达不到要求,所以输出 $-1$。