402230: GYM100703 M It's complicated

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 q₁, q₂, ..., q_n (1 ≤ q_j ≤ 100,  j = 1, 2, ..., n), q_j — the number of units of jth ingredient, which Dragon has.

The third line contains n integers c₁, c₂, ..., c_n (1 ≤ c_j ≤ 10,  j = 1, 2, ..., n), c_j — the number of units of jth ingredient which it needs for cooking a biscuit.

The fourth line contains n integers p₁, p₂, ..., p_n (1 ≤ p_j ≤ 100,  j = 1, 2, ..., n), p_j — cost of a unit of jth ingredient.

Print the only integer — minimum amount of money to spend.

3
15 8 10
2 3 5
12 1 4

148