eolymp
bolt
Try our new interface for solving problems
Problems

Travelling by car - 2

Travelling by car - 2

Time limit 1 second
Memory limit 128 MiB

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 data

First line contains number of cities n (1n10^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 data

Print the minimum possible cost to make the trip.

Examples

Input example #1
5
1 4 5 8 10
6 8 2 4 6
7 2 5 4 7
Output example #1
53
Author Michael Medvediev