G. Ramses' Games
time limit per test
2 seconds
memory limit per test
64 megabytes
input
standard input
output
standard output

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.

Input

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

Each of the next N lines has three integers xi, yi and zi, the dimensions of each block.

Limits

  • 1 ≤ N ≤ 15
  • 1 ≤ xi, yi, zi ≤ 108
Output

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

Examples
Input
5
10 10 10
50 50 50
40 40 40
20 20 20
30 30 30
Output
150
Input
2
20 20 20
30 33 10
Output
33
Input
2
100 10 10
100 12 8
Output
110