24947번 - Team Contest 서브태스크다국어

There are $N$ beavers in JOI University. All of them are working on competitive programming. Each beaver has three abilities: consideration skill, implementation skill, and luck. If the value of an ability is large, it means the level of the ability is high. For each $i$ ($1 ≤ i ≤ N$), the consideration skill of the beaver $i$ is $X_i$, the implementation skill of the beaver $i$ is $Y_i$, and the luck of the beaver $i$ is $Z_i$.

This year, the beavers of JOI University will attend a programming contest for teams. In this contest, the participants solve programming tasks, and each team consists of three beavers. Bitaro is a coach of JOI University. Since teamwork is very important, Bitaro decided to choose three beavers among the $N$ beavers and make a team so that the following condition is satisfied.

Condition Every member in the team has an advantage. This means every member has an ability whose value is strictly larger than the values of the same ability of the other two members.

Among possible teams satisfying the above condition, Bitaro wants to choose a team whose total ability is as large as possible. Here, the total ability of a team is defined as the sum of the maximum value of the consideration skill of the members of the team, the maximum value of the implementation skill of the members of the team, and the maximum value of the luck of the members of the team.

Write a program which, given information of the abilities of each beaver, determines whether it is possible to make a team satisfying the above condition, and, if it is possible to make a team, calculate the maximum possible value of the total ability of a team.

Read the following data from the standard input. Given values are all integers.

$\begin{align*} & N \\ & X_1 \, Y_1 \, Z_1 \\ & X_2 \, Y_2 \, Z_2 \\ & \vdots \\ & X_N \, Y_N \, Z_N \end{align*}$

Write one line to the standard output. The output should contain the maximum possible value of the total ability of a team. If it is impossible to make a team satisfying the condition, output -1.

• $3 ≤ N ≤ 150\,000$.
• $1 ≤ X_i ≤ 100\,000\,000$ ($= 10^8$) ($1 ≤ i ≤ N$).
• $1 ≤ Y_i ≤ 100\,000\,000$ ($= 10^8$) ($1 ≤ i ≤ N$).
• $1 ≤ Z_i ≤ 100\,000\,000$ ($= 10^8$) ($1 ≤ i ≤ N$).