# Travelling by car - 2

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 `cost[k]`

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 `x[k]`

. Also you have to pay `toll[k]`

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 ≤ `10^5`

).

Second line contains n coordinates of cities `x[1]`

, ..., `x[n]`

. Coordinates are unique and sorted, `x[i]`

< `x[i+1]`

for each i = 1, 2, ..., n - 1.

Third line contains n integers - the gasoline costs `cost[1]`

, ..., `cost[n]`

.

Fourth line contains n integers - the entrance payments `toll[1]`

, ..., `toll[n]`

.

Its is knows that cities coordinates, gasoline costs and entrance payments are nonnegative integers, not greater than `10^9`

.

## Output

Print the minimum possible cost to make the trip.