Travelling by car - 2#10777
There are cities. You want to travel from city to city by car. To do this you have to buy some gasoline. It is known that a liter of gasoline costs cost_k in the -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 -th city having coordinate x_k. Also you have to pay toll_k to enter -th city. Your task is to make the trip with minimum possible cost.
First line contains number of cities (1 \le n \le 10^5).
Second line contains coordinates of cities x_1, \ldots, x_n. Coordinates are unique and sorted, x_i < x_{i+1} for each i = 1, 2, \ldots, n - 1.
Third line contains integers - the gasoline costs cost_1, \ldots, cost_n.
Fourth line contains integers - the entrance payments toll_1, \ldots, toll_n.
It is known that cities coordinates, gasoline costs and entrance payments are nonnegative integers, not greater than 10^9.
Print the minimum possible cost to make the trip.
Example 1