[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
University of Science and Technology of China
Online Judge for ACM/ICPC
Processed in 1.5ms with 1 query(s).