#P17806. [Ontak2024]Acm

[Ontak2024]Acm

题目描述

有 nn 名参赛者,第 ii 名参赛者的思考能力、编程能力和幸运程度分别为 xi,yi,zix_i,y_i,z_i。

你需要选出三名不同的参赛者组成队伍。一个队伍是合法的,当且仅当其中每个人都至少有一项属性严格大于另外两个人对应的属性。

例如,一人思考能力严格最高,一人编程能力严格最高,另一人幸运程度严格最高,就构成合法队伍。属性值相等不算严格更高。

一个队伍的实力定义为三项属性的最大值之和。若队伍成员为 a,b,ca,b,c,则其实力为

$$\max(x_a,x_b,x_c)+\max(y_a,y_b,y_c)+\max(z_a,z_b,z_c).$$

求合法队伍的最大实力。如果不存在合法队伍,输出 -1。

输入格式

第一行包含一个整数 nn。

接下来 nn 行,每行包含三个整数 xi,yi,zix_i,y_i,z_i,表示第 ii 名参赛者的三项属性。

输出格式

输出一个整数,表示合法队伍的最大实力;如果不存在合法队伍,输出 -1。

数据范围

3≤n≤150000,1≤xi,yi,zi≤109.3\le n\le150000,\qquad 1\le x_i,y_i,z_i\le10^9.

答案可能超过 32 位有符号整数范围。

样例 1

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

样例 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
15

样例 3

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

子任务

额外限制 分值
n≤300n\le300 8
n≤4000n\le4000 29
xi,yi,zi≤5x_i,y_i,z_i\le5 9
xi,yi,zi≤20x_i,y_i,z_i\le20
xi,yi,zi≤300x_i,y_i,z_i\le300
xi,yi,zi≤4000x_i,y_i,z_i\le4000
无额外限制 27