UOJ Logo Universal Online Judge

UOJ

#727. 【JOISC2022】团队竞技

附件下载 统计

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,否则输出队伍总能力的最大值。

样例一

input

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

output

13

explanation

由海狸 $1,4,5$ 组成的队伍符合条件,因为:

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

总能力值为:$5+4+4=13$。

可以证明这是符合条件的组队中,总能力值最高的队伍。

注意如果选择海狸 $1,3,5$,总能力值将达到 $15$,但是这会导致海狸 $1$ 没有特长。

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

样例二

input

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

output

15

explanation

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

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

样例三

input

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

output

-1

explanation

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

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

数据范围与提示

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

Subtasks

  1. $\text{(8 points) }N\leq 300$
  2. $\text{(29 points) }N\leq 4000$
  3. $\text{(9 points) }X_i,Y_i,Z_i\leq 5~(i\in[1,N])$
  4. $\text{(9 points) }X_i,Y_i,Z_i\leq 20~(i\in[1,N])$
  5. $\text{(9 points) }X_i,Y_i,Z_i\leq 300~(i\in[1,N])$
  6. $\text{(9 points) }X_i,Y_i,Z_i\leq 4000~(i\in[1,N])$
  7. $\text{(27 points)}$ 没有额外限制。

时间限制:$\texttt{2s}$

空间限制:$\texttt{1GB}$