17240번 - Team Selection

PPC라는 온라인 게임은 5명이서 한 팀을 이루어 하는 게임으로, A, B, C, D, E 총 5개의 역할군이 있다. 팀의 각 멤버가 각 역할군 중 서로 다른 하나씩을 맡아 게임이 진행된다.

여러분은 PPC Champions 온라인 게임 대회에 나갈 팀을 모집해야 한다. 팀은 5 명으로 이루어지는데, A, B, C, D, E 5개의 역할군별로 각각 한 명이 필요하다. 여러분이 선택할 수 있는 후보자는 총 n명이 있다. 각 후보자 별로 각 역할군의 실력 이 a_i, b_i, c_i, d_i, e_i로 주어지며, 실력은 0에서 1000 사이의 정수이다. 여러분은 팀을 이룰 5명을 결정하고, 각 멤버가 어떤 역할군을 맡을 지 결정해야 한다. 이 때 5명의 멤버의 역할군의 실력 합이 최대가 되는 팀을 구성하고자 한다.

한 명의 후보자가 두 개의 역할군에서 뛰어난 실력을 가지고 있다고 해서, 그 후보자에게 역할군 두 개를 맡길 수는 없다. 예를 들어 A 실력이 5, B 실력이 5인 사람 두 명을 뽑는 것보다는 A 실력이 6, B 실력이 0인 사람과, A 실력이 0, B 실력이 6인 사람을 뽑는 것이 낫다.

첫 줄에는 후보자의 수 n이 주어진다.(5 ≤ n ≤ 20,000)

두 번째 줄부터 n + 1 번째 각 줄까지 i 번째 후보자의 실력 a_i, b_i, c_i, d_i, e_i가 띄어쓰기를 사이에 두고 주어진다. (0 ≤ a_i, b_i, c_i, d_i, e_i ≤ 1,000)

역할군의 실력 합이 최대가 되는 팀의 실력 합을 출력한다.

첫 번째 예제의 경우 1번 선수에게 A, 2번 선수에게 B, 3번 선수에게 C, 4번 선수에 게 D, 5번 선수에게 E를 맡기는 것이 실력의 합을 극대화 할 수 있다. 6번 선수는 모든 역할군의 실력이 9이지만, 각 역할군에서 6번 선수보다 잘하는 후보자가 있기 때문에, 팀에는 선발되지 않는다.

두 번째 예제의 경우 첫 번째 예제에서, 5번 선수의 D 실력이 20으로 증가한 상황이 다. 이제는 D를 5번 선수에게 맡기고, E를 6번 선수에게 맡길 때 실력의 합을 극대화 할 수 있다.