Description

MedalPluS and his friend NOIRP discovered a veteran game called "Super Marble".

The game is as follows: In an $n \times n$ matrix, there are several enemies. Your marble can destroy enemies, but it can only attack all enemies in your current row and column. You then obtain the sum of their scores. Please choose a position for yourself so that the total score you can obtain is maximized. Note that you cannot stand on a cell occupied by an enemy.

Input Format

The first line contains a positive integer $n$. Then follow $n$ lines, each containing $n$ integers. A positive integer indicates there is an enemy on that cell with that score; $0$ indicates an empty cell.

Output Format

Output a single line containing the maximum score. If there is no place for you to stand (i.e., there is no cell with value $0$), output "Bad Game!".

4
1 1 1 0
1 1 1 1
1 1 1 1
0 1 1 1

6

Hint

Constraints

• For $30\%$ of the testdata, $1 \leq n \leq 10$.
• For $100\%$ of the testdata, $1 \leq n \leq 1000$. It is guaranteed that the number of safe cells is less than $10000$, and the value at each cell does not exceed $1000$.

Translated by ChatGPT 5