Problem B: b 矩阵轰炸

Problem B: b 矩阵轰炸

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 128 MB

Solved: 15Submit: 45Statistics

Description

在一个 N * N 的矩阵中，每个格子上都有敌人，数量为 A[i][j]。你有一枚炸弹，可以炸掉一行和一列（十字形）。炸弹中心位置 (r, c) 的敌人会被消灭，该行该列其他位置也会被消灭。注意中心点只算一次。求选择哪个中心点能消灭最多的敌人？

Input

第一行一个整数 N（1 ≤ N ≤ 10^3）。

下面N行，每行N个整数，表示矩阵。

【数据范围】

30%的数据保证：1<=N<=100  ,0<=A[i][j]<=1000

60%的数据保证：1<=N<=300,0<=A[i][j]<=1000000

100%的数据保证：1<=N<=1000,0<=A[i][j]<=10000000


Output

输出一个整数。

Sample Input Copy 

3
1 2 3
4 5 6
7 8 9

Sample Output Copy 

 33

HINT

样例解释

取点 (3,3)（值为 9）时：

第 3 行和：7 + 8 + 9 = 24

第 3 列和：3 + 6 + 9 = 18

十字形消灭总数 = 行和 + 列和 − 中心点 = 24 + 18 − 9 = 33（最大）

Submit