C - チーム戦 (Team Contest) 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

Score: 100 points

Problem Statement

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 \le i \le 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.

Input

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

N
X_{1} Y_{1} Z_{1}
X_{2} Y_{2} Z_{2}
\vdots
X_{N} Y_{N} Z_{N}

Output

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.

Constraints

  • 3 \le N \le 150\,000.
  • 1 \le X_{i} \le 100\,000\,000 (= 10^{8}) (1 \le i \le N).
  • 1 \le Y_{i} \le 100\,000\,000 (= 10^{8}) (1 \le i \le N).
  • 1 \le Z_{i} \le 100\,000\,000 (= 10^{8}) (1 \le i \le N).

Subtasks

  1. (8 points) N \le 300.
  2. (29 points) N \le 4\,000.
  3. (9 points) X_{i} \le 5,Y_{i} \le 5,Z_{i} \le 5 (1 \le i \le N).
  4. (9 points) X_{i} \le 20,Y_{i} \le 20,Z_{i} \le 20 (1 \le i \le N).
  5. (9 points) X_{i} \le 300,Y_{i} \le 300,Z_{i} \le 300 (1 \le i \le N).
  6. (9 points) X_{i} \le 4\,000,Y_{i} \le 4\,000,Z_{i} \le 4\,000 (1 \le i \le N).
  7. (27 points) No additional constraints.

Sample Input 1

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

Sample Output 1

13

If we make a team consisting of the beaver 1, the beaver 4, and the beaver 5, the condition of the task is satisfied.

  • 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 team are 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 values of 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

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

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

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

Sample Output 3

-1

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.

配点 : 100 点

問題文

JOI 大学には N 匹のビーバーが在籍しており,その全員が競技プログラミングに取り組んでいる.各ビーバーには考察力・実装力・運という 3 種類の能力を表す数値が定められており,それらの値が大きいほど能力が高いことを示す.i 匹目 (1 \leqq i \leqq N) のビーバーの考察力は X_{i},実装力は Y_{i},運は Z_{i} である.

今年,JOI 大学のビーバーたちはチーム対抗のプログラミングコンテストに出場することになった.このコンテストでは,3 匹でチームを組んで競技プログラミングの問題に取り組む.ここで,JOI 大学のコーチであるビ太郎は,チームワークを意識して,以下の条件を満たすように N 匹の中から 3 匹を選んでチームを組むことにした.

  • 条件 どのチームメンバーにも長所がある.すなわち,どのチームメンバーも,他の 2 匹より値が真に大きいような能力を持っている.

ビ太郎は,この条件を満たすなかで可能な限り総合力が高いチームを組みたいと思っている.ここで,チームの総合力は,3 匹のチームメンバーの考察力の最大値,実装力の最大値,運の最大値の 3 つの値の合計として計算される.

各ビーバーの能力の情報が与えられたとき,条件を満たすチームを作ることが可能か判定し,もし可能ならばチームの総合力として考えられる最大の値を求めるプログラムを作成せよ.

入力

入力は以下の形式で標準入力から与えられる.入力される値はすべて整数である.

N
X_{1} Y_{1} Z_{1}
X_{2} Y_{2} Z_{2}
\vdots
X_{N} Y_{N} Z_{N}

出力

標準出力に,チームの総合力として考えられる最大の値を 1 行で出力せよ.ただし,問題文中の条件を満たすようにチームを組むことが不可能な場合は,-1 を出力せよ.

制約

  • 3 \leqq N \leqq 150\,000.
  • 1 \leqq X_{i} \leqq 100\,000\,000 (= 10^{8}) (1 \leqq i \leqq N).
  • 1 \leqq Y_{i} \leqq 100\,000\,000 (= 10^{8}) (1 \leqq i \leqq N).
  • 1 \leqq Z_{i} \leqq 100\,000\,000 (= 10^{8}) (1 \leqq i \leqq N).

小課題

  1. (8 点) N \leqq 300.
  2. (29 点) N \leqq 4\,000.
  3. (9 点) X_{i} \leqq 5,Y_{i} \leqq 5,Z_{i} \leqq 5 (1 \leqq i \leqq N).
  4. (9 点) X_{i} \leqq 20,Y_{i} \leqq 20,Z_{i} \leqq 20 (1 \leqq i \leqq N).
  5. (9 点) X_{i} \leqq 300,Y_{i} \leqq 300,Z_{i} \leqq 300 (1 \leqq i \leqq N).
  6. (9 点) X_{i} \leqq 4\,000,Y_{i} \leqq 4\,000,Z_{i} \leqq 4\,000 (1 \leqq i \leqq N).
  7. (27 点) 追加の制約はない.

入力例 1

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

出力例 1

13

1, 4, 5 匹目のビーバーでチームを組むと,以下のように問題文中の条件を満たす.

  • 1 匹目のビーバーは他の 2 匹よりも運の値が大きい.
  • 4 匹目のビーバーは他の 2 匹よりも実装力の値が大きい.
  • 5 匹目のビーバーは他の 2 匹よりも考察力の値が大きい.

このとき,チームメンバーの考察力・実装力・運の最大値はそれぞれ 5, 4, 4 であるため,チームの総合力は 13 である.総合力を 14 以上にするチームの組み方は存在しないので,13 を出力する.

なお,例えば 1, 3, 5 匹目のビーバーでチームを組むと,チームの総合力は 15 となるものの,1 匹目のビーバーには他のメンバーよりも値が真に大きい能力がないため,問題文中の条件を満たさないことに注意せよ.

この入力例はすべての小課題の制約を満たす.

入力例 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

出力例 2

15

2, 3, 4 匹目のビーバーでチームを組むと,問題文中の条件を満たし,チームの総合力は 15 となる.総合力を 16 以上にするチームの組み方は存在しないので,15 を出力する.

この入力例はすべての小課題の制約を満たす.

入力例 3

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

出力例 3

-1

問題文中の条件を満たすようにチームを組むことはできない.よって -1 を出力する.

この入力例はすべての小課題の制約を満たす.


出典

JOIG 2021/2022 春合宿 Contest Day1 問題3