Problem Statement

Takahashi is a student at Cuboid University (abbreviated: Chokudai).

It is graduation project season at Cuboid University. There is a rumor that anyone at this university who cuts even the slightest corner on their graduation project will be held back a year, so Takahashi wants to make something as good as possible.

Takahashi has decided to build a monument by stacking the $N$ rectangular cuboids he collected in advance for his graduation project. The lengths of the $3$ edges of the $i$-th cuboid are $A_i,B_i,C_i$. The monument must satisfy the following conditions: only one cuboid, that is, exactly $1$ cuboid, may be stacked in direct contact with the top face of any $1$ cuboid; a cuboid whose length or width is larger than that of the cuboid below it must not be stacked on top; and the upper cuboid must be placed so that it has an edge parallel to either the length edge or the width edge of the cuboid below it. Conversely, as long as the above conditions are satisfied, the cuboids may be stacked in any way, and each cuboid may be used in any orientation, assigning its $3$ edges to length, width, and height in any way.

The goodness of a monument is equal to its height. Find the goodness of the best monument Takahashi can build.

(Added at 21:29: You do not need to use all of the cuboids. It is fine to use only 1 cuboid.)

Input

$N$
$A_1\ B_1\ C_1$
$A_2\ B_2\ C_2$
$\vdots$
$A_N\ B_N\ C_N$

$1 \le N \le 16$
$1 \le A_i,B_i,C_i \le 10^7$
All input values are integers.

Output

Output the maximum goodness of a monument Takahashi can build.

Sample

1
1 2 3

3

2
2 7 3
5 1 4

8