#181. 2424. [HAOI2010]订货

2424. [HAOI2010]订货

[HAOI2010] 订货

题目描述

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

输入格式

11 行:$n, m, S \ (0\le n\le50, 0\le m\le10, 0\le S\le10000)$。

22 行:U1,U2,,Un (0Ui10000)U_1 , U_2 , \cdots , U_n \ (0\le U_i\le10000)

33 行:d1,d2,,dn (0di100)d_1, d_2, \cdots ,d_n \ (0\le d_i\le100)

输出格式

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

样例 #1

样例输入 #1

3 1 1000
2 4 8
1 2 4

样例输出 #1

34