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，意义如题中所述。

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

【样例说明】 在实验室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位带符号整数。