The 2nd Japanese Olympiad in Informatics for Girls (JOIG 2021/2022)
Spring Training Camp/Qualifying Trial
March 20–23, 2022 (Komaba, Tokyo)
Contest 1 – Team Contest

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, itmeans the level of the ability is high. For each i (1 ≤ i ≤ N), the consideration skill of the beaver i is Xi , theimplementation skill of the beaver i is Yi , and the luck of the beaver i is Zi .
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 ateam 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 theconsideration skill of the members of the team, the maximum value of the implementation skill of the membersof 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.

Input
Read the following data from the standard input. Given values are all integers.
NX1 Y1 Z1
X2 Y2 Z2..
.
XN YN ZNTeam Contest– 1 / 4

The 2nd Japanese Olympiad in Informatics for Girls (JOIG 2021/2022)
Spring Training Camp/Qualifying Trial
March 20–23, 2022 (Komaba, Tokyo)
Contest 1 – Team Contest

OutputWrite 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.

Constraints• 3 ≤ N ≤ 150 000.
• 1 ≤ Xi ≤ 100 000 000 (= 108 ) (1 ≤ i ≤ N).
• 1 ≤ Yi ≤ 100 000 000 (= 108 ) (1 ≤ i ≤ N).
• 1 ≤ Zi ≤ 100 000 000 (= 108 ) (1 ≤ i ≤ N).

Subtasks
1. (8 points) N ≤ 300.
2. (29 points) N ≤ 4 000.
3. (9 points) Xi ≤ 5，Yi ≤ 5，Zi ≤ 5 (1 ≤ i ≤ N).
4. (9 points) Xi ≤ 20，Yi ≤ 20，Zi ≤ 20 (1 ≤ i ≤ N).
5. (9 points) Xi ≤ 300，Yi ≤ 300，Zi ≤ 300 (1 ≤ i ≤ N).
6. (9 points) Xi ≤ 4 000，Yi ≤ 4 000，Zi ≤ 4 000 (1 ≤ i ≤ N).
7. (27 points) No additional constraints.

Sample Input and Output
Sample Input 1

Sample Output 15133 1 42 3 1
1 5 5
4 4 2
5 2 3
If we make a team consisting of the beaver 1, the beaver 4, and the beaver 5, the condition of the task is
satisfied.

Team Contest– 2 / 4

The 2nd Japanese Olympiad in Informatics for Girls (JOIG 2021/2022)
Spring Training Camp/Qualifying Trial
March 20–23, 2022 (Komaba, Tokyo)
Contest 1 – Team Contest• The value of the luck of the beaver 1 is strictly larger than the values of the luck of the other two members.
• The value of the implementation skill of the beaver 4 is strictly larger than the values of the implementation skill of the other two members.
• The value of the consideration skill of the beaver 5 is strictly larger than the values of the consideration
skill of the other two members.
Then, the maximum values of the consideration skill, implementation skill, luck of the members of the teamare 5, 4, 4, respectively. The total ability of the team is 13. Since it is impossible to make a team whose total
ability is larger than or equal to 14, output 13.
Note that if we make a team consisting of the beaver 1, the beaver 3, and the beaver 5, the total ability
becomes 15. However, since the beaver 1 does not have an ability whose value is strictly larger than the valuesof the same ability of the other two members, the condition of the task is not satisfied.
This sample input satisfies the constraints of all the subtasks.
Sample Input 2

Sample Output 2815

1 1 1
1 1 5
1 5 1
5 1 1
1 5 5
5 1 55 5 1
5 5 5
If we make a team consisting of the beaver 2, the beaver 3, and the beaver 4, the total ability of the team is
15. Since it is impossible to make a team whose total ability is larger than or equal to 16, output 15.
This sample input satisfies the constraints of all the subtasks.
Sample Input 3

Sample Output 3

4-1

1 2 3
1 2 3
1 2 3
1 2 3

Team Contest– 3 / 4

The 2nd Japanese Olympiad in Informatics for Girls (JOIG 2021/2022)
Spring Training Camp/Qualifying Trial
March 20–23, 2022 (Komaba, Tokyo)
Contest 1 – Team Contest

Since it is impossible to make a team satisfying the condition of the task, output -1.
This sample input satisfies the constraints of all the subtasks.

Team Contest– 4 / 4