AIOJ

某公司估计市场在第 $i$ 个月对某产品的需求量为 $U_i$ ，已知在第 $i$ 月该产品的订货单价为 $d_i$ ，上个月月底未销完的单位产品要付存贮费用 $m$ 。

假定第一个月月初的库存量为零，第 $n$ 个月月底的库存量也为零，问如何安排这 $n$ 个月的订购计划，才能使成本最低？

每月月初订购，订购后产品立即到货、进库并供应市场，于当月被售掉则不必付存贮费。假设仓库容量为 $S$ 。

输入格式

第一行三个整数 $n, m, S$ 。

第二行 $n$ 个整数 $U_1, U_2, \dots, U_n$ 。

第三行 $n$ 个整数 $d_1, d_2, \dots, d_n$ 。

只有一行，一个整数，代表最低成本。

3 1 1000
2 4 8
1 2 4

在第 $1$ 个月月初一次性订购 $14$ 件产品，订货费用为 $14\times 1=14$ 。此时第 $1$ 个月月底剩余 $12$ 件、第 $2$ 个月月底剩余 $8$ 件，存贮费用为 $(12+8)\times 1=20$ 。总成本为 $14+20=34$ ，这就是最低成本。

本题为 HAOI 2010 试题「订货」，题面与测试数据整理自 BZOJ 2424。