2907 - 【入门】激光炮
Time Limit : 1 秒
Memory Limit : 128 MB
周周在上电脑课的时候，写了一个游戏。
游戏的内容是：在一个 n\times n 的矩阵里，有若干个敌人。你可以选择一个 没有敌人 的位置放置激光炮，激光炮会朝东南西北四个方向发射激光，具有穿透性能消灭射线上的所有敌人。
现在周周想考考你，把激光炮放置在哪个位置上消灭的敌人数量最多。
Input
第一行一个正整数 n\ (1\le n \le 1000)，表示矩阵的大小。
接下来 n 行，每行 n 个整数 x\ (0 \le x \le 9)，表示敌人的数量，相邻两数之间以一个空格分隔。
Output
一个整数，表示最多能消灭的敌人数量。
Examples
Input
4 1 1 1 0 1 1 0 1 0 0 1 0 0 3 1 1
Output
7
Hint
预处理统计每行每列的敌人数量，保存在两个数组中。遍历矩阵中所有位置，如果当前位置数量为 0，用刚才预处理的数组计算当前行列敌人数量之和，取最大值。
时间复杂度 \mathcal{O}(n^2)。