시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB27413410051.020%

문제

이 문제는 C번 사각형 게임 (Small) 문제와 $N$ 제한만 다르고 동일한 문제입니다.

어느 날, 강의실에서 수업을 듣던 민우는 지루함을 참지 못하고 그만 노트에 $N\times N$ 크기의 격자를 그려버리고 말았습니다. 격자의 칸이 비어있으면 허전하니, 민우는 격자의 각 칸에 정수 $S_{ij}$ 도 써넣었습니다. 그러고 나서 민우는 옆자리에서 졸고 있던 종진이에게 간단한 게임을 제안했습니다. 게임의 규칙은 아래와 같습니다.

  1. 민우가 먼저 $N$개의 행 중 $0$개 이상의 행을 고르고, 선택한 행에 속한 모든 칸들을 색칠합니다.
  2. 그다음엔 종진이가 $N$개의 열 중 $0$개 이상의 열을 고르고, 선택한 열에 속한 모든 칸들을 색칠합니다.
  3. 어떤 칸이 민우와 종진이에 의해 모두 색칠되었다면, 그 칸에 적힌 수만큼 종진이가 점수를 얻습니다.
  4. 어떤 칸이 민우와 종진이에 의해 모두 색칠되지 않았다면, 그 칸에 적힌 수만큼 종진이가 점수를 얻습니다.
  5. 어떤 칸이 민우나 종진이 중 한 명에게만 색칠되었다면, 그 칸에 적힌 수만큼 민우가 점수를 얻습니다.

민우와 종진이는 모두 자신의 점수가 최대가 되도록 최선의 전략을 이용해 게임을 할 것입니다. 이때 민우가 얻을 수 있는 최대 점수를 구해봅시다.

입력

첫 번째 줄에는 격자판의 크기를 의미하는 정수 $N$이 주어집니다. $( 1 \le N \le 18 )$

두 번째 줄부터 $N+1$ 번째 줄에는 절댓값이 $10^9$ 보다 작거나 같은 $N$개의 정수가 공백으로 구분되어 주어집니다. $i+1$ 번째 줄에서 $j$ 번째로 주어진 정수는 격자판의 $(i, j)$ 칸에 적힌 수 $S_{ij}$ 를 의미합니다.

출력

첫 번째 줄에 민우가 얻을 수 있는 최대 점수를 출력합니다.

예제 입력 1

3
5 3 2
3 2 1
2 4 3

예제 출력 1

10

예제 입력 2

6
430293690 307875894 395554936 504301925 867090770 723452020
932682466 825405919 780518550 119438341 409889255 282168792
285122954 160505810 162418616 828469018 770972884 465837003
406103158 346601330 843767649 120722675 8356905 304009207
444009037 918559736 16139414 506669809 75384216 623030704
520571801 824386365 833141090 445214833 179846100 493359817

예제 출력 2

7432796756

노트

이 문제는 Python3를 이용하여 풀 수 있음이 보장되지 않습니다. Python3를 이용하는 분들은 Python3과 같은 문법을 가지면서 일반적으로 더 빠르게 동작하는 PyPy3를 이용해 제출하는 것을 권장드립니다.

출처

University > DGIST > 2022 DGIST 현풍전산배 알고리즘 대회 D번