Background

JOISC2022 D2T3.

Problem Description

There are $N$ beavers at JOI University, and they all participate in competitive programming. Each beaver has three ability values: thinking, acting, and luck. A larger value means the beaver is stronger in that ability. For the $i$-th beaver $i~(i\in[1,N])$, its thinking value is $X_i$, its acting value is $Y_i$, and its luck value is $Z_i$.

This year, the beavers at JOI University will take part in a team competitive programming contest. A team consists of three members. Bitaro is the coach of JOI University. Since teamwork is important, Bitaro decides to choose three beavers from the $N$ beavers to form a team, and these three beavers must satisfy the following requirement:

Condition: Every member has their own advantage. This means that for each member, there exists an ability value that is strictly greater than the corresponding ability values of the other two members.

Among all teams that satisfy the condition, Bitaro wants to choose the team with the strongest total ability. The total ability of a team is defined as the sum of the maximum thinking value among the three members, the maximum acting value among the three members, and the maximum luck value among the three members.

Determine whether there exists a team that satisfies the condition. If yes, compute the maximum possible total ability of such a team.

Input Format

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

Each of the next $N$ lines contains three integers $X_i,Y_i,Z_i$, representing the ability values of the beaver.

Output Format

Output one integer. If there is no team that satisfies the condition, output -1. Otherwise, output the maximum total ability of a team.

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

13

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

15

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

-1

Hint

Sample Explanation #1

A team consisting of beavers $1,4,5$ satisfies the condition, because:

1. Beaver $1$'s advantage is luck.
2. Beaver $4$'s advantage is acting.
3. Beaver $5$'s advantage is thinking.

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

It can be proven that this team has the highest total ability among all teams that satisfy the condition.

Note that if we choose beavers $1,3,5$, the total ability would reach $15$, but this would cause beaver $1$ to have no advantage.

This sample satisfies the constraints of all subtasks.

Sample Explanation #2

The optimal team is: beavers $2,3,4$.

This sample satisfies the constraints of all subtasks.

Sample Explanation #3

Any way of forming a team would cause some member to have no advantage, so there is no team that satisfies the condition.

This sample satisfies the constraints of all subtasks.

Constraints

For all testdata:

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

The additional constraints and scores of the subtasks are shown in the table below:

Translated by ChatGPT 5