318014 - 仓库建设

学院有N个实验室,由高到低分布在一座山上。如图18.14所示,实验室1在山顶,实验室N在山脚。

      /\ 1
     /   \   2
    /      \
   /         \  3
  /            \
 /               \
/                  \ N

由于这座山处于高原内陆地区(干燥少雨),管理员一般把道具直接堆放在露天,以节省费用。突然有一天,管理员被告知三天之后将有一场暴雨,于是管理员决定紧急在某些实验室建立一些仓库以免道具被淋坏。由于地形的不同,在不同实验室建立仓库的费用可能是不同的。第i个工厂目前已有成品Pi件,在第i个实验室位置建立仓库的费用是Ci。对于没有建立仓库的实验室,其道具应被运往其他的仓库进行储藏,而由于道具的对外销售处设置在山脚的实验室N,故道具只能往山下运(即只能运往编号更大的实验室的仓库),当然运送道具也是需要费用的,假设一件道具运送1个单位距离的费用是1。假设建立的仓库容量都是足够大的,可以容下所有的道具。你将得到以下数据:1:实验室i距离实验室1的距离Xi(其中X1=0);2:实验室i目前已有成品数量Pi;3:在实验室i建立仓库的费用Ci;请你帮助管理寻找一个仓库建设的方案,使得总的费用(建造费用+运输费用)最小。

输入

第一行包含一个整数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,不如前者优。 【数据规模】 对于100%的数据,N≤1 000 000。所有的Xi,Pi,Ci均在32位带符号整数以内,保证中间计算结果不超过64位带符号整数。

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题