사각형 게임 (Small)

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

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

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

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

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

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

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

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