Description

A company estimates that in month $i$ the market demand for a certain product is $U_i$. It is known that the unit purchase price in month $i$ is $d_i$. For each unit of product that remains unsold at the end of a month and is carried over to the next month, a storage fee of $m$ must be paid. Assume the initial inventory at the beginning of month $1$ is $0$, and the inventory at the end of month $n$ is also $0$. How should the ordering plan for these $n$ months be arranged to minimize the total cost?

Orders are placed at the beginning of each month. After ordering, products arrive immediately, enter the warehouse, and supply the market. If a unit is sold within the same month, no storage fee is charged for it. Assume the warehouse capacity is $S$.

Input Format

Line $1$: $n, m, S \ (0\le n\le50, 0\le m\le10, 0\le S\le10000)$.

Line $2$: $U_1 , U_2 , \cdots , U_n \ (0\le U_i\le10000)$.

Line $3$: $d_1, d_2, \cdots ,d_n \ (0\le d_i\le100)$.

Output Format

Only $1$ line, an integer representing the minimum cost.

3 1 1000
2 4 8
1 2 4 

34

Hint

Translated by ChatGPT 5