Warehouse Construction Optimization

L Company has n factories arranged from the top to the bottom of a mountain, with factory 1 at the top and factory n at the bottom. The distance from factory 1 to factory i is given as \(x_i\) (with \(x_1=0\)). Factory i currently produces \(p_i\) items, and if a warehouse is built at factory i, the building cost is \(c_i\).

If a warehouse is not built at a factory, its products must be transported downwards (i.e. to a factory with a larger index) to a factory that has a warehouse. The transportation cost is 1 per product per unit distance. Note that a warehouse built at a factory has unlimited capacity, and it will also store the products already produced at that factory.

Your task is to choose a set of factories (which must include factory n) where warehouses will be built such that the total cost (warehouse building cost plus transportation cost) is minimized.

The transportation cost for a factory that does not have a warehouse is calculated as follows: if factory \(i\) does not build a warehouse and its products are transported to the next factory \(j\) (\(j>i\)) that has a warehouse, then the cost is \(p_i\times (x_j-x_i)\). The cost for a factory where a warehouse is built is simply \(c_i\). The overall cost is the sum of the building costs for factories where a warehouse is built and the transportation costs for all other factories.

Hint: You may use dynamic programming with the recurrence

\[ DP(i)=\min_{j=i \ldots n}\Bigl\{ c_j+\Bigl( x_j\Bigl(\sum_{k=i}^{j-1}p_k\Bigr)-\sum_{k=i}^{j-1}p_kx_k\Bigr)+DP(j+1) \Bigr\} \]

with the boundary condition \(DP(n+1)=0\); note that when \(j=i\), the inner sum is zero.

inputFormat

The first line of input contains a single integer n (the number of factories).

The second line contains n space-separated integers \(x_1,x_2,\ldots,x_n\) denoting the distance of each factory from factory 1. It is guaranteed that \(x_1=0\) and \(x_i \lt x_{i+1}\) for all valid i.

The third line contains n space-separated integers \(p_1,p_2,\ldots,p_n\) where \(p_i\) denotes the number of products at factory i.

The fourth line contains n space-separated integers \(c_1,c_2,\ldots,c_n\) where \(c_i\) is the cost of building a warehouse at factory i.

outputFormat

Output a single integer, which is the minimum total cost to protect all products.

sample

3
0 1 3
10 20 30
100 50 0

60