class="markdown_views prism-atelier-sulphurpool-light">

题目大意

有n种灯泡，不同种类的灯泡需要同种电源，同种灯泡只需一个电源。你现在要设计一个照明系统，给出n种灯泡的电压V，电源费用K，一个灯泡的费用C和所需该种灯泡数量L，电压小的灯泡可以被电压大的灯泡代替，求最小花费。

题目分析

由人类的直觉，我们应该把灯泡按照电压从大到小排序，以方便处理。
推理1：一种灯泡要么全部替换为另一种，要么都不换。
证明：
如果将灯泡t全部替换为灯泡i比都不替换优，那么说明：
ki+ci∗(li+lt)<ki+kt+ci∗li+ct∗lt
那么ci∗lt<kt+ct∗lt
已经将t都换为i后，如果将部分灯泡换回t的话，还要再买一个电源，花费kt，并且灯泡价格依据式子并不会带来什么优惠。
同理，如果不换更优，那么再换一部分，由于ci∗lt>kt+ct∗lt，也不会带来任何优惠。
状态转移：令sum[i]表示电压按照从大到小排序后，灯泡数量前缀和。f[i]表示前i种灯泡处理好的最小价格。
由人类的直觉，我们认为状态转移方程为：
f[i]=min(f[i],f[j−1]+kj+(sum[i]−sum[j−1])∗cj)(j≤i)
为什么可以直接替换一个区间呢？见推理2.
推理2：状态转移方程正确性证明。
证明：
设vi>vj>vt
如果t被i替换比较优的前提下，j不被t替换更优（即状态转移方程的反例）则：
ki+(li+lj+lt)∗ci>ki+kj+(li+lt)∗ci+lj∗cj
即：ci∗lj>cj∗lj+kj
即：ci>cj
然而出现这种反例也没关系，因为如果出现如上情况，我们让j到i之间的灯泡全被j替换更优。现在我们证明这一点，则要证:
ki+kj+(li+lt)∗ci+lj∗cj>ki+kj+li∗ci+(lt+lj)∗cj
即要证：lt∗ci>