There are n cities. You want to travel from city 1 to city n by car. To do this you have to buy some gasoline. It is known that a liter of gasoline costs costk in the k-th city. Initially your fuel tank is empty and you spend one liter of gasoline per kilometer. Cities are located on the same line in ascending order with k-th city having coordinate xk. Also you have to pay tollk to enter k-th city. Your task is to make the trip with minimum possible cost.

Input

First line contains number of cities n (1 ≤ n ≤ 105).

Second line contains n coordinates of cities x1, ..., xn. Coordinates are unique and sorted, xi < xi+1 for each i = 1, 2, ..., n - 1.

Third line contains n integers - the gasoline costs cost1, ..., costn.

Fourth line contains n integers - the entrance payments toll1, ..., tolln.

Its is knows that cities coordinates, gasoline costs and entrance payments are nonnegative integers, not greater than 109.

Output

Print the minimum possible cost to make the trip.