| [Home|Training|Problems|Contests|C Language] | [Login|Register] |
|
Problems Status Rank |
Problem 1067
Block
Time Limit: 1000ms
Memory Limit: 65536kb Description
小朋友们有 N 种不同的积木,每种积木长为 X i ,宽为 Y i ,高为 Z i ,数量有无限多个,现在他们要开始搭积木啦! 搭积木的规则很简单: 1、积木要一块搭在另一块上面,这样一块一块的搭上去。 2、如果 A 积木在 B 积木上面,那么必须满足 A 的底长和底宽都小于 B 的长和宽。 现在小朋友们想知道,他们最高能将积木搭到多少高度。 TIPS:积木当然是可以翻转的啦! Input
多 CASE 输入对于每个 CASE: 第一行将是一个正整数 N(1<=N<=300)表示有 N 种积木 接下来 N 行,每行 3 个整数 Xi , Yi , Zi 分别表示积木的长,宽和高 ( 1<=Xi ,Yi ,Zi <=10^9)。 Output
对每个测试数据, 输出一行答案。
Sample Input
2 6 8 10 5 5 5 7 1 1 1 2 2 2 3 3 3 4 4 4 5 5 5 6 6 6 7 7 7 5 31 41 59 26 53 58 97 93 23 84 62 64 33 83 27 Sample Output
40 21 28 342 |