3372. 套娃

单点时限: 2.0 sec

内存限制: 256 MB

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

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

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

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

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

输入格式

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

输出格式

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

样例

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

5 人解决,6 人已尝试。

7 份提交通过,共有 62 份提交。

7.3 EMB 奖励。

创建: 2 年,1 月前.

修改: 2 年,1 月前.

最后提交: 1 年,11 月前.

来源: JSOI 2015

题目标签