3372. 套娃

单点时限: 2.0 sec

内存限制: 256 MB

刚从俄罗斯旅游回来的 JYY 买了很多很多好看的套娃作为纪念品!JYY 由于太过激动,把所有的套娃全部都打开了。而由于很多套娃长得过于相像,JYY 现在不知道该如何把它们装回去了(他实在搞不清,应该把哪个套娃装到哪个里面去了)。

JYY 一共有 $N$ 个拆开的套娃,每个套娃从 $1$ 到 $N$ 编号。编号为 $i$ 的套娃有一个外径 $Out_i$ 和一个内径 $In_i$ $(In_i<Out_i)$。对于套娃 $i$ 和套娃 $j$,如果满足 $Out_i<In_j$,那么套娃 $i$ 就可以装到套娃 $j$ 里面去。注意,一个套娃内部,不允许并排的放入多个套娃。也就是说,如果我们将 $i$ 装到 $j$ 的内部之后,还存在另一个套娃 $k$,也满足 $Out_k<In_j$,我们此时是不允许再将 $k$ 放到 $j$ 内部的(因为 $j$ 的内部已经放入了 $i$)。但是,如果 $k$ 还满足 $Out_k<In_i$,那么我们允许先将 $k$ 放到 $i$ 的内部,然后再把 $k$ 和 $i$ 作为一个整体放入 $j$ 的内部。

JYY 认为一套好的套娃,内部的空隙一定是尽量少的。如果套娃 $j$ 内部装入了套娃 $i$,那么我们认为,套娃 $j$ 内部产生的空隙为 $In_j-Out_i$;如果套娃 $j$ 的内部什么也没有装,那么套娃 $j$ 的空隙则就是 $In_j$。

JYY 也希望,那些长得更加好看的套娃,里面可以填的尽量满一些;而相对那些不那么好看的套娃,JYY 也就相对不那么介意一些。为此 JYY 对于编号为 $i$ 的套娃设置了一个好看度 $B_i$,如果这个套娃内部还存在 $K$ 的空隙,那么 JYY 对于这个套娃就会产生 $K \cdot B_i$ 的不满意度。JYY 对于一个套娃安装方案的不满意度,就是每个套娃产生的不满意度的总和。

JYY 希望找出一个,不满意度最小的套娃安装方案。

输入格式

第一行包含一个正整数 $N$。接下来 $N$ 行,每行包含三个正整数 $Out_i,In_i,B_i$,表示 $i$ 号套娃的外径,内径,以及好看度。

$N \leq 2 \cdot 10^5,1 \leq In_i < Out_i \leq 10^4,1 \leq B_i \leq 10^9$。

输出格式

输出文件包含一行一个整数,表示不满意度的最小值。

样例

Input
3
5 4 1
4 2 2
3 2 1
Output
7

8 人解决,9 人已尝试。

11 份提交通过,共有 69 份提交。

6.2 EMB 奖励。

创建: 2 年,12 月前.

修改: 2 年,12 月前.

最后提交: 6 月,3 周前.

来源: JSOI 2015

题目标签