Team Selection

PPC is an online game played by teams of 5, with five roles: A, B, C, D, and E. Each member of a team takes a different one of these roles.

You must recruit a team to compete in the PPC Champions online game tournament. A team consists of 5 people, and one person is needed for each of the five roles A, B, C, D, and E. There are n candidates you can choose from. For each candidate, their skill in each role is given as ai, bi, ci, di, ei, and each skill is an integer between 0 and 1000. You must decide on the 5 people who will form the team and which role each member will take. You want to form the team whose total skill across the roles is maximized.

Just because a candidate has high skill in two roles does not mean you can assign two roles to that candidate. For example, picking two people with A skill 5 and B skill 5 is worse than picking one person with A skill 6 and B skill 0 and another with A skill 0 and B skill 6.

The first line gives the number of candidates n. (5 ≤ n ≤ 20,000)

From the second line to the n + 1-th line, the skills ai, bi, ci, di, ei of the i-th candidate are given, separated by spaces. (0 ≤ ai, bi, ci, di, ei ≤ 1,000)

Print the total skill of the team that maximizes the sum of skills across the roles.

In the first example, the sum of skills is maximized by assigning A to competitor 1, B to competitor 2, C to competitor 3, D to competitor 4, and E to competitor 5. Competitor 6 has skill 9 in every role, but is not selected for the team because some candidate is better than competitor 6 in every role.

The second example is the same as the first, except that competitor 5's D skill has increased to 20. Now the sum of skills is maximized by assigning D to competitor 5 and E to competitor 6.