사각형 게임 (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를 사용한다면 문법은 같으면서 일반적으로 더 빠르게 동작하는 PyPy3로 제출하는 것을 권장합니다.