Dragon was drinking tea on a balcony and admiring a very beautiful sunset. Two outgoing silhouettes were still descrying in the rays of a setting sun. Of course, Princess promised to visit Dragon sometime, but what could be a reason for her to come back in the Castles Valley?..
Dragon decided to cook biscuits according to a recipe that was told him by Princess. So he needs to check if he has sufficient quantity of ingredients for it. Of course, he has a few of ginger, cinnamon, cloves and cardamon... But, comparing to making tea, he needs some more ingredients to bake biscuits.
Dragon revised all his ingredients, and knew how many units of each ingredient he had.
It was written in the recipe how many units of each ingredient are required to bake a biscuit. Certainly, Dragon wanted to bake an integer number of biscuits.
Dragon realized that he will expend some ingredients completely, while some other ingredients will remain. He believed he must purchase some extra ingredients, so that all ingredients will be completely expended after baking some number of biscuits.
Dragon knew the cost for a unit of each ingredient. Your task is to figure out minimum amount of money which is needed to spend to fulfil the condition above.
The first line contains integer n (1 ≤ n ≤ 10) — the number of ingredients.
The second line contains n integers q1, q2, ..., qn (1 ≤ qj ≤ 100, j = 1, 2, ..., n), qj — the number of units of jth ingredient, which Dragon has.
The third line contains n integers c1, c2, ..., cn (1 ≤ cj ≤ 10, j = 1, 2, ..., n), cj — the number of units of jth ingredient which it needs for cooking a biscuit.
The fourth line contains n integers p1, p2, ..., pn (1 ≤ pj ≤ 100, j = 1, 2, ..., n), pj — cost of a unit of jth ingredient.
Print the only integer — minimum amount of money to spend.
## Input
The first line contains integer n (1 ≤ n ≤ 10) — the number of ingredients.The second line contains n integers q1, q2, ..., qn (1 ≤ qj ≤ 100, j = 1, 2, ..., n), qj — the number of units of jth ingredient, which Dragon has.The third line contains n integers c1, c2, ..., cn (1 ≤ cj ≤ 10, j = 1, 2, ..., n), cj — the number of units of jth ingredient which it needs for cooking a biscuit.The fourth line contains n integers p1, p2, ..., pn (1 ≤ pj ≤ 100, j = 1, 2, ..., n), pj — cost of a unit of jth ingredient.
## Output
Print the only integer — minimum amount of money to spend.
[samples]
**Definitions**
Let $ n \in \mathbb{Z}^+ $ be the number of ingredients.
Let $ \mathbf{q} = (q_1, \dots, q_n) \in \mathbb{Z}^n $ be the available units of each ingredient.
Let $ \mathbf{c} = (c_1, \dots, c_n) \in \mathbb{Z}^n $ be the units required per biscuit for each ingredient.
Let $ \mathbf{p} = (p_1, \dots, p_n) \in \mathbb{Z}^n $ be the cost per unit of each ingredient.
Let $ k \in \mathbb{Z}^+ $ be the number of biscuits to bake.
**Constraints**
1. $ 1 \leq n \leq 10 $
2. $ 1 \leq q_j \leq 100 $ for all $ j \in \{1, \dots, n\} $
3. $ 1 \leq c_j \leq 10 $ for all $ j \in \{1, \dots, n\} $
4. $ 1 \leq p_j \leq 100 $ for all $ j \in \{1, \dots, n\} $
**Objective**
Find the minimum cost:
$$
\min_{k \in \mathbb{Z}^+} \sum_{j=1}^{n} p_j \cdot \left( (k \cdot c_j) \bmod q_j \right)
$$
where the deficit for ingredient $ j $ is $ (k \cdot c_j - q_j) \bmod c_j $ if $ k \cdot c_j > q_j $, else $ c_j - (q_j \bmod c_j) $ if $ q_j \bmod c_j \neq 0 $, and 0 otherwise.
Equivalently, for each $ j $, define the additional units needed for $ k $ biscuits as:
$$
d_j(k) = \begin{cases}
0 & \text{if } q_j \equiv 0 \pmod{c_j} \text{ and } k \equiv 0 \pmod{q_j / c_j} \\
(k \cdot c_j - q_j) \bmod c_j & \text{if } k \cdot c_j \geq q_j \\
c_j - (q_j \bmod c_j) & \text{if } k \cdot c_j < q_j \text{ and } q_j \bmod c_j \neq 0
\end{cases}
$$
But since $ k $ must be chosen so that **all** $ q_j + \text{purchased}_j $ are divisible by $ c_j $, we require:
$$
k \cdot c_j \geq q_j \quad \text{and} \quad k \cdot c_j \equiv 0 \pmod{\gcd(c_j, q_j)} \quad \text{(redundant)}
$$
Actually, simpler:
We need $ k \cdot c_j \geq q_j $ and $ k \cdot c_j \equiv 0 \pmod{c_j} $ (always true), so we require:
$$
k \geq \left\lceil \frac{q_j}{c_j} \right\rceil \quad \text{for all } j
$$
Then the amount to buy for ingredient $ j $ is:
$$
b_j(k) = k \cdot c_j - q_j
$$
Total cost:
$$
C(k) = \sum_{j=1}^{n} p_j \cdot (k \cdot c_j - q_j)
$$
Subject to:
$$
k \geq \max_{1 \leq j \leq n} \left\lceil \frac{q_j}{c_j} \right\rceil
$$
**Objective (Final)**
$$
\min_{k \in \mathbb{Z},\, k \geq \max_j \left\lceil \frac{q_j}{c_j} \right\rceil} \sum_{j=1}^{n} p_j (k c_j - q_j)
$$