题目描述

题目译自 JOISC 2022 Day2 T3「チーム戦 / Team Contest」
译文由 hehezhou 友情提供。

JOI 大学有 $N$ 只海狸，他们都参与竞技编程。每只海狸有三项能力值：思考值、行动值 和 运气值。如果一个能力值很大，意味着他这项能力比较强大。对于第 $i$ ($i \in [1, N]$) 只海狸，他的思考值为 $X_i$，行动值为 $Y_i$，运气值为 $Z_i$。

今年 JOI 大学的海狸们将参与一场团体竞技编程，一支队伍由三名队员组成。Bitaro 是 JOI 大学的教练，由于团队合作很重要，Bitaro 决定从 $N$ 只海狸中选出三只海狸组成队伍，这三只海狸要满足以下条件：

条件：每个成员都有自己的优势，这意味着每个成员都有一项能力值严格大于其他两人的对应能力值。

在所有符合条件的组队中，Bitaro 想要选一个总能力最强的队伍，一个队伍的总能力定义为：
三人最大思考值、三人最大行动值和三人最大运气值之和。

请你求出，是否存在一个符合条件的组队，如果是，计算队伍总能力可能的最大值。

---

输入格式

第一行一个整数 $N$ 表示海狸数。

接下来 $N$ 行，每行三个整数 $X_i, Y_i, Z_i$ 表示海狸的各项能力值。

---

输出格式

一行一个整数，如果不存在符合条件的组队，输出 $-1$，否则输出队伍总能力的最大值。

---

样例 1

输入

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

输出

13

解释
由海狸 $1, 4, 5$ 组成的队伍符合条件，因为：

• 海狸 $1$ 的优势是运气。
• 海狸 $4$ 的优势是行动。
• 海狸 $5$ 的优势是思考。

总能力值为：$5 + 4 + 4 = 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

输出

15

最优组队为：海狸 $2, 3, 4$。

这组样例满足所有子任务的限制。

---

样例 3

输入

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

输出

-1

任何组队方式都会导致队员没有特长，不存在符合条件的组队。

这组样例满足所有子任务的限制。

---

数据范围与提示

对于所有数据，满足：

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

详细子任务附加限制及分值如下表所示：

子任务编号	附加限制	分值
1	$N \leq 300$	8
2	$N \leq 4000$	29
3	$X_i, Y_i, Z_i \leq 5(i∈[1,N])$	9
4	$X_i, Y_i, Z_i \leq 20(i∈[1,N])$
5	$X_i, Y_i, Z_i \leq 300(i∈[1,N])$
6	$X_i, Y_i, Z_i \leq 4000(i∈[1,N])$
7	无附加限制	27

---