Problem Background

JOISC2022 D2T3

Problem Description

JOI University has $N$ beavers, all of whom participate in competitive programming. Each beaver has three ability scores: thinking, action, and luck. A high score in an ability indicates a strong capability in that area. For the $i$-th beaver (where $i \in [1, N]$), their thinking score is $X_i$, action score is $Y_i$, and luck score is $Z_i$.

This year, the beavers of JOI University will participate in a team competitive programming competition, where a team consists of three members. Bitaro is the coach of JOI University, and due to the importance of teamwork, Bitaro has decided to select three beavers from the $N$ beavers to form a team, with the following condition:

Condition: Each member must have a dominant ability, meaning each member has one ability score that is strictly higher than the corresponding scores of the other two members.

Among all teams that meet this condition, Bitaro wants to select the team with the highest total ability. The total ability of a team is defined as the sum of the highest thinking score, the highest action score, and the highest luck score among the three members.

Your task is to determine if there exists a team that meets the condition, and if so, calculate the maximum possible total ability of such a team.

Input Format

The first line contains an integer $N$, representing the number of beavers.

The next $N$ lines each contain three integers $X_i, Y_i, Z_i$, representing the ability scores of each beaver.

Output Format

Output a single integer. If no team meets the condition, output -1. Otherwise, output the maximum total ability of a team.

Sample Input and Output

Sample Input #1

5
3 1 4
2 3 1
1 5 5
4 4 2
5 2 3

Sample Output #1

13

Sample Input #2

8
1 1 1
1 1 5
1 5 1
5 1 1
1 5 5
5 1 5
5 5 1
5 5 5

Sample Output #2

15

Sample Input #3

4
1 2 3
1 2 3
1 2 3
1 2 3

Sample Output #3

-1

Notes

Sample Explanation #1

The team formed by beavers $1, 4, 5$ meets the condition because:

1. Beaver $1$ has a dominant luck score.
2. Beaver $4$ has a dominant action score.
3. Beaver $5$ has a dominant thinking score.

The total ability is: $5 + 4 + 4 = 13$.

It can be proven that this is the team with the highest total ability among those that meet the condition.

Note that selecting beavers $1, 3, 5$ would result in a total ability of $15$, but this would cause beaver $1$ to lack a dominant ability.

This sample meets the constraints of all subtasks.

Sample Explanation #2

The optimal team is formed by beavers $2, 3, 4$.

This sample meets the constraints of all subtasks.

Sample Explanation #3

Any team formation would result in members lacking dominant abilities, so no team meets the condition.

This sample meets the constraints of all subtasks.

Data Range

For all data, the following constraints are satisfied:

• $3 \leq N \leq 150000$.
• $1 \leq X_i, Y_i, Z_i \leq 10^8$ for $1 \leq i \leq N$.

Detailed subtask additional constraints and scores are as follows:

见题面 Input 部分

见题面 Output 部分