【问题描述】

某公司估计市场在第 i 个月对某产品的需求量为 Ui，已知在第 i月该产品的订货单价为 di，上个月月底未销完 的单位产品要付存贮费用 m，假定第一月月初的库存量为零，第 n 月月底的库存量也为零，问如何安排这 n 个月订购计划，才能使成本最低？每月月初订购，订购后产品立即到货，进库并供应市场，于当月被售掉则不必付存贮费。假设仓库容量为 s。

【输入格式】

第 1 行：n,m,S(0≤n≤50,0≤m≤10,0≤S≤10000)。

第 2 行：U1,U2,…,Ui,…,Un(0≤Ui≤10000)。

第 3 行：d1,d2,…,di,…,dn(0≤di≤100)。

【输出格式】

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

【输入样例】

3 1 1000
2 4 8
1 2 4

【输出样例】

34