Maximum Hamburgers

Kai, the lobster, runs a hamburger shop. To make one hamburger, he needs (n) ingredients. For each ingredient (i), he has (x_i) units available. He has two hamburger recipes. The first recipe requires (a_i) units of ingredient (i), and the second recipe requires (b_i) units. When making a hamburger, Kai can choose either recipe. Find the maximum number of hamburgers Kai can produce using the available ingredients.

More formally, let (t) be the total number of hamburgers produced and let (s) be the number of hamburgers made using the first recipe. Then for each ingredient (i) the following inequality must hold: [ s \times a_i + (t-s) \times b_i \le x_i, \quad \text{for } i=1,2,\dots,n. ] Your task is to determine the maximum possible (t) for which there exists an integer (s) with (0\le s\le t) satisfying all the inequalities.

inputFormat

The input begins with an integer (n) representing the number of ingredients.\n\nThe second line contains (n) space-separated integers (x_1,x_2,\dots,x_n), where (x_i) denotes the available units of ingredient (i).\n\nThe third line contains (n) space-separated integers (a_1,a_2,\dots,a_n), describing the units required for ingredient (i) in the first recipe.\n\nThe fourth line contains (n) space-separated integers (b_1,b_2,\dots,b_n), describing the units required for ingredient (i) in the second recipe.

outputFormat

Output a single integer, the maximum number of hamburgers that can be produced.

sample

1
10
2
3

5