题目描述

小杨在一个实验中搭建了一个 $n \times n$ 的靶场网格。网格中某些位置放有靶标(用正整数表示分值)，某些位置为空(用 $0$ 表示)。小杨可以在一个空位上放置激光器，激光器会摧毁与其同行、同列的所有靶标，摧毁靶标的总分即为这些靶标的分值之和。

请帮小杨找到一个最佳的激光器放置位置，使得摧毁的靶标总分最大。注意激光器只能放在没有靶标的位置上。如果网格中不存在任何空位，则输出 Bad Game!。

输入格式

第一行一个正整数 $n$，表示网格的边长。

接下来 $n$ 行，每行 $n$ 个整数，第 $i$ 行第 $j$ 列的值 $a_{i,j}$ 表示该位置的靶标分值($0$ 表示空位)。

输出格式

输出一个整数，表示最大摧毁总分。如果不存在空位，输出 Bad Game!。

样例

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

6

提示

【数据范围】

对于 $30\%$ 的数据，$1\leq n\leq 10$；

对于 $100\%$ 的数据，$1\leq n\leq 1000$，保证空位数量小于 $10000$，每个位置靶标分值不超过 $1000$。