Description

Company A is seeing strong sales of a certain computer product. As the CEO of Company A, Xiao A plans to make a detailed production and sales plan for the next consecutive $N$ sales quarters. It is known that in the $i$-th sales quarter the order quantity is $D_i$. In quarter $i$, Company A may meet the orders in the following ways:

• Produce new products in quarter $i$ to sell.
• If there is remaining inventory before quarter $i$, it can be sold directly in quarter $i$ (note that there is no inventory before the first quarter).
• In quarter $i$, it is allowed to leave part of the orders unfilled and postpone them, merging them into the order quantity of the next quarter $(i + 1)$.

Company A needs to consider the following costs: the production cost for new products, the additional storage cost for inventory, and the compensation paid to users for delayed orders. Moreover, due to labor and resource limitations, the number of new products that can be produced in each sales quarter is limited, and both the costs and production upper bounds differ by quarter, as follows:

• In quarter $i$, at most $U_i$ new units can be produced, and the cost per unit is $P_i$.
• Products kept at the end of quarter $i$ for use in later quarters incur a storage fee: for each unit kept from quarter $i$ to quarter $i + 1$, an extra fee of $M_i$ must be paid (note that once kept to the next quarter, the product may remain in inventory again).
• For each unit postponed from quarter $i$ and merged into the next quarter’s order quantity, Company A must compensate users $C_i$ (note that an order postponed to the next quarter may be postponed again, and the fee is charged according to the later quarter’s delay fee).

By the end of quarter $N$, Company A must have fulfilled all user orders. It is guaranteed that the total number of units the company can produce is not less than the total order quantity; that is, there exists at least one production and sales plan that satisfies all orders. Xiao A wants to know how to arrange production and sales so that, while satisfying all orders, the total cost is minimized.

Input Format

The first line of the input file $\tt{product.in}$ contains a positive integer $N$, the number of sales quarters.

The second line contains $N$ non-negative integers $D_1, D_2, \ldots, D_N$, where $D_i$ is the order quantity in quarter $i$.

The third line contains $N$ non-negative integers $U_1, U_2, \ldots, U_N$, where $U_i$ is the maximum number of new units that can be produced in quarter $i$.

The fourth line contains $N$ non-negative integers $P_1, P_2, \ldots, P_N$, where $P_i$ is the per-unit production cost in quarter $i$.

The fifth line contains $N - 1$ non-negative integers $M_1, M_2, \ldots, M_{N-1}$, where $M_i$ is the additional storage fee to keep one unit from quarter $i$ to quarter $i + 1$.

The sixth line contains $N - 1$ non-negative integers $C_1, C_2, \ldots, C_{N-1}$, where $C_i$ is the compensation paid if one unit’s order is not fulfilled in quarter $i$ and is merged into the order quantity of quarter $i + 1$.

Output Format

The output file $\tt{product.out}$ contains a single non-negative integer, the minimal total cost.

4
3 2 1 2
2 5 2 2
5 1 5 5
1 2 1
5 3 3

30

Hint

Sample Explanation:

In the first quarter, produce $2$ units. In the second quarter, produce $5$ units. In the third quarter, produce no units. In the fourth quarter, produce $1$ unit. The production cost is $2 * 5 + 5 * 1 + 0 * 5 + 1 * 5 = 20$.

Since at most $2$ units can be produced in the first quarter, the $3$-unit order cannot be fully met; thus $1$ unit is postponed to the second quarter, incurring a compensation of $5$.

In the second quarter, because $1$ unit was postponed from the first quarter, the order quantity becomes $3$. This quarter produces $5$ units, leaving $2$ units in inventory. In the third quarter, sell directly from inventory; the extra $1$ unit is further stored to the fourth quarter. Together with producing $1$ unit in the fourth quarter, all orders are satisfied. The total storage cost is $2 * 2 + 1 * 1 = 5$.

The total cost is $20 + 5 + 5 = 30$.

Constraints:

• For $30\%$ of the testdata, $N \leq 1{,}000$.
• For $100\%$ of the testdata, $1 \leq N \leq 100{,}000$, $1 \leq D_i, U_i, P_i, M_i, C_i \leq 10{,}000$.

Translated by ChatGPT 5