BABTWR  Tower of Babylon
Apart from the Hanging Gardens the Babylonians (around 3000539 b.c.) built the Tower of Babylon as well. The tower was meant to reach the sky, but the project failed because of a confusion of language imposed from much higher above.
For the 2638th anniversary a model of the tower will be rebuilt. n different types of blocks are available. Each one of them may be duplicated as many times as you like. Each type has a height y, a width x and a depth z. The blocks are to be stacked one upon eachother so that the resulting tower is as high as possible. Of course the blocks can be rotated as desired before stacking. However for reasons of stability a block can only be stacked upon another if both of its baselines are shorter.
Input
The number of types of blocks n is located in the first line of each test case. On the subsequent n lines the height y_{i}, the width x_{i} and the depth z_{i} of each type of blocks are given. There are never more than 30 different types available.
There are many test cases, which come one by one. Input terminates with n = 0.
Edited: You can assume that max(x_{i}, y_{i}, z_{i}) <= 2500.
Output
For each test case your program should output one line with the height of the highest possible tower.
Example
Sample input: 5 31 41 59 26 53 58 97 93 23 84 62 64 33 83 27 1 1 1 1 0 Sample output: 342 1
hide comments
cpp219:
20200207 16:20:10
good DP problem :) worth doing before searching for solution 

karan_yadav:
20180725 13:24:21
Quite tough if you haven't solved any longest increasing subsequence problem yet. Still worth a try before looking for hints/solution. 

aman_sachin200:
20180613 18:52:38
Quite easy with TopDown <3 :P!!!!Keep in mind the six rotations possible!!! 

shiv2111:
20180119 09:13:37
6 rotations possible... good one. 

aman_9899:
20170621 16:21:08
box stacking problem ..!!!


cake_is_a_lie:
20170228 15:18:02
This can be solved in O(N log N), but it's a bit tricky. There is a pretty obvious O(N^2) solution and even more obvious O(N^3) that should still not TLE I think.


flyingduchman_:
20161223 05:49:40
Learn dp solution of LIS(longest increasing subsequence)first. Then learn "box stacking algorithm"the problem is of. As it's not an adhoc, you are unlikely to invent or discover the solution 

razor123:
20161109 16:02:17
3 rotations are possible if u keep (depth > width). 

ashish22_dwd:
20161007 15:26:38
My 50th with this nice problem :) 

hamjosh1:
20160925 09:26:55
easy :'D

Added by:  MichaĆ Czuczman 
Date:  20040706 
Time limit:  3s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 
Resource:  Swiss Olympiad in Informatics 2004 