3263 - 仓库建设

通过次数

4

提交次数

5

时间限制 : 1 秒
内存限制 : 128 MB
15654413346984.png

输入

第一行包含一个整数N,表示工厂的个数。

接下来N行每行包含两个整数Xi,Pi,Ci,意义如题中所述。

输出

输出仅包含一个整数,为可以找到最优方案的费用。

样例

输入

3
0 5 10
5 3 100
9 6 10

输出

32

提示

【样例输出解释】

在工厂1和工厂3建立仓库,建立费用我10+10=20,运输费用为(9-5)*3=12,总费用32。

如果仅在工厂3建立仓库,建立费用为10,运输费用为(9-0)*5+(9-5)*3=57,总费用67,不如前者优。

【数据规模】

对于20%的数据,N≤500。

对于40%的数据,N≤10000.

来源

动规专题