[HAOI2010]订货

某公司估计市场在第 $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

样例输出

34

样例解释

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

数据范围

• $0\le n\le 50$；
• $0\le m\le 10$；
• $0\le S\le 10^4$；
• $0\le U_i\le 10^4$；
• $0\le d_i\le 100$。

来源与许可

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

样例 1

输入

3 1 1000
2 4 8
1 2 4

输出

34