Coding is the closest thing we have to superpower !

1180 : 综合练习-cannons
描述

超能侠在上电脑课的时候,写了一个游戏。

游戏的内容是:在一个 n \times n 的矩阵里,有若干个敌人。你可以选择一个 没有敌人 的位置放置激光炮,激光炮会朝东南西北四个方向发射激光,具有穿透性,能消灭射线上的所有敌人。

现在超能侠想考考你,把激光炮放置在哪个位置上消灭的敌人数量最多。

输入

第一行一个正整数 n(1 \leq n \leq 100), 表示矩阵的大小。

接下来 n 行, 每行 n 个整数 x(0 \leq x \leq 9), 表示敌人的数量。

输出

一个整数,表示最多能消灭的敌人数量。

样例

输入

4
1 1 1 0
1 1 0 1
0 0 1 0
0 3 1 1

输出

7
语言:
主题: