← 返回题目列表

AtCoder · abc338_c

E. 剩下的食谱

中文机器翻译题面 查看原题

分数: 300 点

问题陈述

您的冰箱有 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.

您可以用以下材料制作一份 A 菜 100 成分克数 1 和 100 成分克数 2,一份 B 菜 200 成分克数 1 和 10 成分克数 2.

要制作两份 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

你可以使 8 A 菜份量 800 成分克数 1,和 30 菜 B 的份量 300 成分克数 2,总共 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