Production Planning and Cost Minimization

Company A is currently enjoying brisk sales of a computer product. As the CEO, Xiao A is planning the production and sales scheme for the upcoming N sales quarters. In the i-th quarter, the demand (order quantity) is given by \(D_i\). To satisfy these orders, the company may use the following methods in quarter \(i\):

• Produce new products in quarter \(i\) at a cost \(P_i\) per unit, with a production capacity limit of \(U_i\) units.
• Sell products from previous quarters’ production which have been stored. For each product stored from quarter \(i\) to \(i+1\), a storage cost of \(M_i\) per unit is incurred (and if stored further, the cost is incurred each time).
• Delay fulfilling part of the demand. Any unit of demand delayed from quarter \(i\) to quarter \(i+1\) incurs a penalty cost of \(C_i\). Note that if an order gets delayed over several quarters, the penalty cost will be applied in each quarter according to that quarter's delay fee.

At the end of quarter \(N\), all pending orders must be satisfied. It is guaranteed that the total production capacity over all quarters is no less than the total demand, so there exists at least one feasible production/sales plan. Your task is to determine the arrangement of production and sales in order to meet all orders while minimizing the total cost.

The cost to supply a unit of order from quarter i produced in quarter j (with \(j \ge i\)) is given by:

\[ \text{cost}(i,j) = P_j + \sum_{t=i}^{j-1}(M_t + C_t), \quad \text{with } \text{cost}(i,i)=P_i. \]

In addition, the total production in quarter \(j\) cannot exceed \(U_j\). Compute the minimum total cost to satisfy all orders.

inputFormat

The input is given in five lines:

1. An integer \(N\) (the number of quarters).
2. N space‐separated integers: \(D_1\) \(D_2\) ... \(D_N\) (the order quantities in each quarter).
3. N space‐separated integers: \(U_1\) \(U_2\) ... \(U_N\) (the production capacities for each quarter).
4. N space‐separated integers: \(P_1\) \(P_2\) ... \(P_N\) (the production cost per unit in each quarter).
5. N-1 space‐separated integers: \(M_1\) \(M_2\) ... \(M_{N-1}\) (the storage cost per unit when storing from quarter \(i\) to \(i+1\)).
6. N space‐separated integers: \(C_1\) \(C_2\) ... \(C_N\) (the penalty cost per unit for delaying orders from quarter \(i\) to the next quarter; note that the penalty applies each time an order is delayed).

You can assume that \(\sum_{i=1}^{N} U_i \ge \sum_{i=1}^{N} D_i\) and that for each quarter \(i\), the production capacity in the subsequent quarters is sufficient to cover the demand if needed.

outputFormat

Output a single integer representing the minimum total cost to meet all orders.

sample

3
10 5 15
15 15 15
5 4 3
1 2
2 3 4

115