JOI 大学有 $N$ 只海狸。它们都在从事竞技编程。每只海狸都有三种能力：思考能力、实现能力和运气。如果某项能力的值很大，则意味着该项能力的水平很高。对于每只海狸 $i$ ($1 \le i \le N$)，其思考能力为 $X_i$，实现能力为 $Y_i$，运气为 $Z_i$。

今年，JOI 大学的海狸们将参加一场团队编程竞赛。在这场竞赛中，参赛者解决编程任务，每个团队由三只海狸组成。Bitaro 是 JOI 大学的教练。由于团队合作非常重要，Bitaro 决定从 $N$ 只海狸中选出三只组成一个团队，使得以下条件得到满足。

条件：团队中的每名成员都具有一项优势。这意味着每名成员都拥有一项能力，其值严格大于其他两名成员在该项能力上的值。

在满足上述条件的所有可能团队中，Bitaro 希望选择一个总能力尽可能大的团队。这里，团队的总能力定义为团队成员中思考能力的最大值、实现能力的最大值以及运气最大值之和。

编写一个程序，在给定每只海狸能力信息的情况下，确定是否可以组成满足上述条件的团队，如果可以，计算团队总能力的最大可能值。

输入格式

从标准输入读取以下数据。给定值均为整数。

$N$ $X_1 \ Y_1 \ Z_1$ $X_2 \ Y_2 \ Z_2$ $\vdots$ $X_N \ Y_N \ Z_N$

输出格式

向标准输出写入一行。输出应包含团队总能力的最大可能值。如果无法组成满足条件的团队，则输出 $-1$。

数据范围

• $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$)

子任务

1. (8 分) $N \le 300$
2. (29 分) $N \le 4\,000$
3. (9 分) $X_i \le 5, Y_i \le 5, Z_i \le 5$ ($1 \le i \le N$)
4. (9 分) $X_i \le 20, Y_i \le 20, Z_i \le 20$ ($1 \le i \le N$)
5. (9 分) $X_i \le 300, Y_i \le 300, Z_i \le 300$ ($1 \le i \le N$)
6. (9 分) $X_i \le 4\,000, Y_i \le 4\,000, Z_i \le 4\,000$ ($1 \le i \le N$)
7. (27 分) 无附加限制

样例

样例输入 1

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

样例输出 1

13

说明 1

如果我们选择海狸 1、海狸 4 和海狸 5 组成团队，则满足任务条件。

• 海狸 1 的运气值严格大于其他两名成员的运气值。
• 海狸 4 的实现能力值严格大于其他两名成员的实现能力值。
• 海狸 5 的思考能力值严格大于其他两名成员的思考能力值。

此时，团队成员思考能力、实现能力和运气值的最大值分别为 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

如果我们选择海狸 2、海狸 3 和海狸 4 组成团队，团队的总能力为 15。由于无法组成总能力大于或等于 16 的团队，输出 15。

该样例输入满足所有子任务的限制。

样例输入 3

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

样例输出 3

-1

说明 3

由于无法组成满足任务条件的团队，输出 -1。

该样例输入满足所有子任务的限制。