← 返回题目列表

AtCoder · zone2021_c

C. 疯狂团队

中文机器翻译题面 查看原题

分数: 400 点

问题陈述

你想从 N 候选人中选择三个人组成一支队伍。
每个候选人有五个参数:力量、速度、技巧、知识和创造力。
第 i名候选人的力量、速度、技巧、知识和创造力为 A_i, B_i, C_i, D_i,和 E_i。
。让我们将你们团队的力量定义为成员力量的最大值。团队的速度、技巧、知识和创造力的定义方式类似。
然后,让我们将你们团队的总体实力定义为团队的力量、速度、技巧、知识和创造力的最小值。
找出你们团队总实力的最大可能值。

约束

  • 输入中的所有值都是整数。
  • 3 ≤ N ≤ 3000
  • 1 ≤ A_i, B_i, C_i, D_i, E_i ≤ 10^9

输入

输入由标准输入按以下格式给出:

N
A_1 B_1 C_1 D_1 E_1
A_2 B_2 C_2 D_2 E_2
\vdots
A_N B_N C_N D_N E_N

输出

打印答案。


示例输入 1

3
3 9 6 4 6
6 9 3 1 1
8 8 9 3 7

示例输出 1

4

我们只能选择他们三个。
那么,团队的参数将如下所示:

  • 力量: \max(3, 6, 8) = 8;
  • 速度: \max(9, 9, 8) = 9;
  • 技巧: \max(6, 3, 9) = 9;
  • 知识: \max(4, 1, 3) = 4;
  • 创造力: \max(6, 1, 7) = 7.

团队的总实力将为 \min(8, 9, 9, 4, 7) = 4.


示例输入 2

5
6 13 6 19 11
4 4 12 11 18
20 7 19 2 5
15 5 12 20 7
8 7 6 18 5

示例输出 2

13

如果我们选择 1-st, 2-nd,和 3-名候选人,团队的总实力将为 \min(20, 13, 19, 19, 18) = 13.


示例输入 3

10
6 7 5 18 2
3 8 1 6 3
7 2 8 7 7
6 3 3 4 7
12 8 9 15 9
9 8 6 1 10
12 9 7 8 2
10 3 17 4 10
3 1 3 19 3
3 14 7 13 1

示例输出 3

10