403164: GYM101055 G Ramses' Games

Ramses II was the most prestigious of the Egyptian pharaohs. He reigned from 1279 BC to 1213 BC, and built many temples, including the famous Nubian temples. The most famous is built on stone, in Abu Simpel, near the second Nilo fall, where he is also sculptured.

With Nefertari and many other wives he had probably more than 6 children, with whom he liked to play a game called "highest pyramid". The game was played the following way: The kids got some blocks of different dimensions (that could be rotated), and should with these cubes build a pyramid as high as they could. To build it they could not place a bigger block over a smaller one, that is, if the block A is over block B, then both the width and the depth of A should not exceed B's.

Amen-hotep, Ramses' firstborn, was very good in this game, and many times he was able to build pyramids higher than his dad could. Ramses decided to call the court's mathematician, Narmer, to find, for each set of blocks, the highest pyramid possible.

The first line has a single integer N, the number of blocks.

Each of the next N lines has three integers x_i, y_i and z_i, the dimensions of each block.

Limits

• 1 ≤ N ≤ 15
• 1 ≤ x_i, y_i, z_i ≤ 10⁸

Print a single integer, the height of the highest pyramid that is possible to build with the blocks.

5
10 10 10
50 50 50
40 40 40
20 20 20
30 30 30

150

2
20 20 20
30 33 10

33

2
100 10 10
100 12 8

110