E - Towers
Problem
The famous Babylonian King Samsu-Iluna was fascinated by the stars that He could see on the night sky. He believed that if He could build a tower tall enough He could touch them and fulfill His destiny as divine ruler of the Babylonians. To be able to build this tower He created large quarries where they dug and cut the largest stone blocks they could find. Once the number of stone blocks seemed large enough to build the tower, He ordered His best engineers to do so, but they came to the terrible conclusion that not all blocks could stay on top others.
The problem was that, although all blocks measured the same and all where roughly of cubic form, with six faces, not all weighted the same, and heavier blocks could not be placed on top of lighter ones. In addition to that, and due to technological problems, block faces came in all sort of shapes. This fact is important, because to put one block on top of another, the two touching faces must have the same shape. After a long study, the engineers were able to categorize all the existing shapes, but due to the large number of different shapes and blocks, they weren’t sure how to arrange the blocks in order to build the tallest tower possible.
Aware of this problem the King
promised to give half of His fortune to anyone able to stack the given blocks
to build the tallest possible tower. Your objective is to write a program to
calculate the size of such tallest
tower.
Input
The input file may contain a
sequence of various test cases. The first line of each test case contains a
positive integer N (not larger
than 1000) indicating the number of blocks in the test case. Each of the
following N lines will contain the description of one block. Each block
is described by a sequence of seven integer numbers: the first gives the
weight of the block (a positive integer), and the following six numbers give
the shapes of each of the block sides, in the following order: front, back,
left, right, top and bottom. Shapes are classified by integers in the range 1
to 1000 (including 1 and 1000), and no two blocks have the same weight. The
input terminates by giving the value -1 for N.
Output
For each test case in the input file, the output file must contain a line with a single integer, indicating the number of blocks in the tallest tower that may be built with the blocks in the corresponding test case.
Sample Input
3
1
1 2 2 2
1 2
2
3 3 3 3
3 3
3
3 2 1 1 1
1
10
150
1 2 3 4 5 6
100
1 5 10 3 6 5
170
6 1 2 3 4 7
120
5 7 3 2 1 9
160
10 9 8 7 6 5
130
1 3 3 5 8 10
140
6 6 2 2 4 4
180
1 2 3 3 2 1
110
2 6 7 3 6 9
190
3 2 1 1 2 3
-1
Sample Output
2
8