축구 대회

시간 제한1초메모리 제한1024 MB

요약
N명 중 11명을 골키퍼 한 명, 나머지 포지션마다 최소 한 명씩 뽑아 선호도 합의 최댓값을 구한다.
난이도

보통10점 중 6점

유형
그리디, 정렬, 동적 계획법
정답자
아직 제출이 없습니다

문제

설날을 맞아, 도훈이네 부대에서 축구 대회를 개최한다고 한다! 도훈이는 팀의 감독으로서, 팀에 소속될 1111명의 선수를 선발하는 역할을 맡게 되었다.

팀에 선발할 선수는 각각 공격수, 미드필더, 수비수, 골키퍼의 네 가지 포지션 중 하나로 등록되어야 하며, 각 포지션에는 반드시 최소 한 명씩은 선발해야 한다. 단, 골키퍼는 한 명만 선발해야 한다.

도훈이의 팀에 지원한 선수들은 지원서에 각각 공격수, 미드필더, 수비수, 골키퍼에 대한 선호도 a_ia\_i, b_ib\_i, c_ic\_i, d_id\_i를 작성하여 제출했다. 팀의 만족도는 각 선수들이 선발된 포지션에 대한 선호도의 합이다. 도훈이는 해당 정보를 바탕으로, 팀 선발 조건에 맞게 팀의 만족도를 최대화하는 방식으로 선수들을 선발하고자 한다. 도훈이를 위해, 팀 선발 조건에 맞게 1111명을 선발한 경우 팀의 만족도의 최댓값을 구해주자.

입력

첫 번째 줄에 부대 내 병사 수 NN이 주어진다.

이후 NN개의 줄에 걸쳐, i+1i+1번째 줄에 ii번째 병사의 공격수, 미드필더, 수비수, 골키퍼 포지션별 선호도 a_ia\_i, b_ib\_i, c_ic\_i, d_id\_i가 공백으로 구분되어 주어진다.

출력

팀 선발 조건에 맞게 선수들을 선발했을 때 팀의 만족도의 최댓값을 출력한다.

제한

  • 11≤N≤200,00011 \le N \le 200\\,000
  • 1≤a_i≤1081 \le a\_i \le 10^8
  • 1≤b_i≤1081 \le b\_i \le 10^8
  • 1≤c_i≤1081 \le c\_i \le 10^8
  • 1≤d_i≤1081 \le d\_i \le 10^8
  • 모든 입력은 정수이다.

예제1

  1. 예제 1

    입력
    11
1 1 1 1
2 2 2 2
5 5 5 5
3 3 3 3
5 5 5 5
2 2 2 2
8 8 8 8
7 7 7 7
5 5 5 5
4 4 4 4
1 1 1 1
    예상 출력
    43