MAD TEAM

AtCoder

IDzone2021_c

Time2000ms

Memory256MB

Difficulty—

You want to choose three persons from $N$ candidates to form a team. Each candidate has five parameters: power, speed, technique, knowledge, and inventiveness. The power, speed, technique, knowledge, and the inventiveness of the $i$\-th candidate are $A_i$, $B_i$, $C_i$, $D_i$, and $E_i$, respectively. Let us define your team's power as the maximum of the members' powers. The team's speed, technique, knowledge, and inventiveness are defined similarly. Then, let us define your team's total strength as the minimum of the team's power, speed, technique, knowledge, and inventiveness. Find the maximum possible value of your team's total strength. ## Constraints * All values in input are integers. * $3 ≤ N ≤ 3000$ * $1 ≤ A_i, B_i, C_i, D_i, E_i ≤ 10^9$ ## Input Input is given from Standard Input in the following format: $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$ [samples]

Samples

Input #1

Output #1

4

We have no choice but to choose all three of them.  
Then, the team's parameters will be as follows:

*   power: $\max(3, 6, 8) = 8$;
*   speed: $\max(9, 9, 8) = 9$;
*   technique: $\max(6, 3, 9) = 9$;
*   knowledge: $\max(4, 1, 3) = 4$;
*   inventiveness: $\max(6, 1, 7) = 7$.

Thus, the team's total strength will be $\min(8, 9, 9, 4, 7) = 4$.

Input #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

Output #2

13

If we choose the $1$\-st, $2$\-nd, and $3$\-rd candidates, the team's total strength will be $\min(20, 13, 19, 19, 18) = 13$.

Input #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

Output #3

API Response (JSON)

{
  "problem": {
    "name": "MAD TEAM",
    "description": {
      "content": "You want to choose three persons from $N$ candidates to form a team.   Each candidate has five parameters: power, speed, technique, knowledge, and inventiveness.   The power, speed, technique, knowled",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "zone2021_c"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You want to choose three persons from $N$ candidates to form a team.  \nEach candidate has five parameters: power, speed, technique, knowledge, and inventiveness.  \nThe power, speed, technique, knowled...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments