C - Leftover Recipes Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300 点

問題文

冷蔵庫に N 種類の材料があります。これらを材料 1、\dots、材料 N と呼びます。材料 i は Q_i グラムあります。

あなたは 2 種類の料理を作れます。料理 A は、1 人分を作るのに各材料 i (1 \leq i \leq N) が A_i グラム必要です。料理 B は、1 人分を作るのに各材料 i が B_i グラム必要です。どちらも整数人分しか作れません。

冷蔵庫にある材料のみを使って、最大で合計何人分の料理を作れますか。

制約

  • 1 \leq N \leq 10
  • 1 \leq Q_i \leq 10^6
  • 0 \leq A_i \leq 10^6
  • A_i \geq 1 であるような i が存在する。
  • 0 \leq B_i \leq 10^6
  • B_i \geq 1 であるような i が存在する。
  • 入力値はすべて整数である。

入力

入力は以下の形式で標準入力から与えられる。

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 を 1 人分作れ、200 グラムの材料 1 と 10 グラムの材料 2 で料理 B を 1 人分作れます。

料理 A を 2 人分、料理 B を 3 人分作るのに必要な材料 1 の量は 100 \times 2 + 200 \times 3 = 800 グラム、材料 2 の量は 100 \times 2 + 10 \times 3 = 230 グラムで、いずれも冷蔵庫にある量を超えません。このようにして合計 5 人分の料理を作ることができますが、6 人分を作る方法はなく、答えは 5 です。

入力例 2

2
800 300
100 0
0 10

出力例 2

38

800 グラムの材料 1 で料理 A を 8 人分、300 グラムの材料 2 で料理 B を 30 人分、合計 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

Score: 300 points

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