Building blocks (p11) Introduction The Babylonians had n types of blocks, and an unlimited supply of blocks of each type. Each type-i block was a rectangular solid with linear dimensions. A block could be reoriented so that any two of its three dimensions determined the dimensions of the base and the other dimension was the height. They wanted to construct the tallest tower possible by stacking blocks. The problem was that, in building a tower, one block could only be placed on top of another block as long as the two base dimensions of the upper block were both strictly smaller than the base dimensions of the lower block. This meant, for example, that blocks oriented to have equal-sized bases couldn't be stacked on top of each other. Problem Your job is to write a program that determines the height of the tallest tower the babylonians could build with a given set of blocks. Input The input will consist of several test cases. The first line of each case will be n, which is the number of types of each block. It will then be followed by n lines, which will give the dimensions of the blocks of each type. The input will be terminated by a value of 0 for n. Output For each case, you have to output the maximum height of the tower that could be built by using the given blocks. Sample Input 4 2 3 4 7 3 1 4 2 6 1 3 9 2 5 7 3 2 8 5 0 Sample Output 11 8 |