103382: [Atcoder]ABC338 C - Leftover Recipes

Problem Statement

Your refrigerator has $N$ kinds of ingredients. Let us call them ingredient $1$, $\dots$, ingredient $N$. You have $Q_i$ grams of ingredient $i$.

You can make two types of dishes. To make one serving of dish A, you need $A_i$ grams of each ingredient $i$ $(1 \leq i \leq N)$. To make one serving of dish B, you need $B_i$ grams of each ingredient $i$. You can only make an integer number of servings of each type of dish.

Using only the ingredients in the refrigerator, what is the maximum total number of servings of dishes you can make?

Constraints

• $1 \leq N \leq 10$
• $1 \leq Q_i \leq 10^6$
• $0 \leq A_i \leq 10^6$
• There is an $i$ such that $A_i \geq 1$.
• $0 \leq B_i \leq 10^6$
• There is an $i$ such that $B_i \geq 1$.
• All input values are integers.

Input

The input is given from Standard Input in the following format:

$N$
$Q_1$ $Q_2$ $\dots$ $Q_N$
$A_1$ $A_2$ $\dots$ $A_N$
$B_1$ $B_2$ $\dots$ $B_N$

Output

Assuming that you can make a maximum total of $S$ servings of dishes, print the integer $S$.

Sample Input 1

2
800 300
100 100
200 10

Sample Output 1

5

This refrigerator has $800$ grams of ingredient $1$ and $300$ grams of ingredient $2$.

You can make one serving of dish A with $100$ grams of ingredient $1$ and $100$ grams of ingredient $2$, and one serving of dish B with $200$ grams of ingredient $1$ and $10$ grams of ingredient $2$.

To make two servings of dish A and three servings of dish B, you need $100 \times 2 + 200 \times 3 = 800$ grams of ingredient $1$, and $100 \times 2 + 10 \times 3 = 230$ grams of ingredient $2$, neither of which exceeds the amount available in the refrigerator. In this way, you can make a total of five servings of dishes, but there is no way to make six, so the answer is $5$.

Sample Input 2

2
800 300
100 0
0 10

Sample Output 2

38

You can make $8$ servings of dish A with $800$ grams of ingredient $1$, and $30$ servings of dish B with $300$ grams of ingredient $2$, for a total of $38$ servings.

Sample Input 3

2
800 300
801 300
800 301

Sample Output 3

0

You cannot make any dishes.

Sample Input 4

10
1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000
0 1 2 3 4 5 6 7 8 9
9 8 7 6 5 4 3 2 1 0

Sample Output 4

222222

问题描述

你的冰箱里有$N$种食材。我们分别称它们为食材1，$\dots$，食材$N$。你有$Q_i$克食材$i$。

你可以做两种类型的菜肴。要制作一份菜肴A，你需要$A_i$克每种食材$i$ $(1 \leq i \leq N)$。要制作一份菜肴B，你需要$B_i$克每种食材$i$。每种菜肴只能制作整数份。

仅使用冰箱里的食材，你最多可以制作多少份菜肴？

约束条件

• $1 \leq N \leq 10$
• $1 \leq Q_i \leq 10^6$
• $0 \leq A_i \leq 10^6$
• 存在一个$i$使得$A_i \geq 1$。
• $0 \leq B_i \leq 10^6$
• 存在一个$i$使得$B_i \geq 1$。
• 所有输入值都是整数。

输入

输入从标准输入以以下格式给出：

$N$
$Q_1$ $Q_2$ $\dots$ $Q_N$
$A_1$ $A_2$ $\dots$ $A_N$
$B_1$ $B_2$ $\dots$ $B_N$

输出

假设你最多可以制作$S$份菜肴，打印整数$S$。

样例输入1

2
800 300
100 100
200 10

样例输出1

5

这个冰箱里有$800$克食材1和$300$克食材2。

你可以用$100$克食材1和$100$克食材2制作一份菜肴A，用$200$克食材1和$10$克食材2制作一份菜肴B。

要制作两份菜肴A和三份菜肴B，你需要$100 \times 2 + 200 \times 3 = 800$克食材1和$100 \times 2 + 10 \times 3 = 230$克食材2，这两者都不超过冰箱里的可用量。这样，你可以制作总共五份菜肴，但是没有方法可以制作六份，所以答案是$5$。

样例输入2

2
800 300
100 0
0 10

样例输出2

38

你可以用$800$克食材1制作$8$份菜肴A，用$300$克食材2制作$30$份菜肴B，总共制作$38$份菜肴。

样例输入3

2
800 300
801 300
800 301

样例输出3

0

你不能制作任何菜肴。

样例输入4

10
1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000
0 1 2 3 4 5 6 7 8 9
9 8 7 6 5 4 3 2 1 0

样例输出4

222222