Team Selection for Unique Advantages

JOI University has \(N\) beavers, each with three ability values: thinking, action, and luck. The \(i\)-th beaver has ability values \(X_i\), \(Y_i\), and \(Z_i\) respectively.

This year, the beavers will compete in a team programming contest. A team consists of exactly three members selected from the \(N\) beavers. The coach, Bitaro, wants each member of the team to have a unique advantage. This means that for each team member, there exists at least one ability in which their value is strictly greater than that of the other two team members. In other words, there exists a permutation of the three abilities \((X, Y, Z)\) such that if a beaver is assigned one ability, its corresponding value is strictly greater than the values of the other two beavers in that same ability.

For any valid team consisting of beavers \(i, j, k\), the team's total ability is defined as:

\(\max(X_i, X_j, X_k) + \max(Y_i, Y_j, Y_k) + \max(Z_i, Z_j, Z_k)\)

Your task is to determine whether there exists a valid team satisfying the above condition. If one exists, compute the maximum possible total ability among all valid teams. Otherwise, output -1.

Note: A team is valid if and only if, for each ability (thinking, action, luck), the maximum value among the three members is unique (i.e. occurs exactly once).

inputFormat

The first line of input contains an integer \(N\) representing the number of beavers.

Each of the following \(N\) lines contains three space-separated integers \(X_i\), \(Y_i\), and \(Z_i\) that represent the thinking, action, and luck values for the \(i\)-th beaver.

outputFormat

Output a single integer, which is the maximum total ability among all valid teams. If no valid team exists, output -1.

sample

3
10 1 1
1 10 1
1 1 10

30