#3785. 「一本通 5.6 练习 2」仓库建设 暂未评定

原题来自：ZJOI 2007

L 公司在山上有 个工厂。如图所示，工厂 在山顶，工厂 在山脚。

由于地形的不同，在不同工厂建立仓库的费用可能不同。工厂 目前已有成品 件，在该厂建立仓库的费用为 。对于没有建立仓库的工厂，其产品应被运往其他的仓库进行储藏，而由于 L 公司产品的对外销售处设置在山脚的工厂 ，故产品只能往山下运（即只能运往编号更大的工厂的仓库），当然运送产品也是需要费用的，假设一件产品运送 个单位距离的费用是 。假设建立的仓库容量都都是足够大的，可以容下所有的产品。
已知：

1. 工厂 距离工厂 的距离 （其中 ）；
2. 工厂 目前已有成品数量 ；
3. 在工厂 建立仓库的费用 。

请你帮助 L 公司寻找一个仓库建设的方案，使得总的费用（建造费用+运输费用）最小。

第一行包含一个整数 ，表示工厂的个数。
接下来 行，每行包含三个整数 ，意义如题中所述。

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

样例输入

3
0 5 10
5 3 100
9 6 10

样例输出

32

样例说明

在工厂 和工厂 建立仓库，建立费用为 ，运输费用为 ，总费用 。如果仅在工厂 建立仓库，建立费用为 ，运输费用为 ，总费用 ，不如前者优。

对于全部数据，，保证所有的 均在 int 范围以内，保证中间计算结果不超过 long long 范围。