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. \InputFile 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 $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$. \OutputFile Print the minimum possible cost to make the trip.