Travelling by car

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 $cos{t}_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 $tol{l}_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\le n\le 1000)$.

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 $cos{t}_1,...,cos{t}_n$.

Fourth line contains $n$ integers — the entrance payments $tol{l}_1,...,tol{l}_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.

Examples