题目描述

最近疫情比较严重，因此希蒙觉得把他的所有亲朋好友叫了出来，并让他们按照一个 N*N 的矩阵站好,现在每个人都有一个数值表示他有多容易被感染，现在要找出它的风险最大的子矩阵, 要求这个子矩阵是正方形, 即长和宽相等。

定义一个矩阵的风险值为：将这个矩阵主对角线上的数的和定义为 A, 另一条对角线上的数的和定义为 B, 则这个矩阵的风险值为 A - B 的结果 。

输入格式

输入的第一行包含一个正整数 $N$。

接下来 $N$ 行每行包含 $N$ 个整数，表示这个矩阵。

输出格式

输出一行一个整数，表示最大的风险值。

样例 #1

样例输入 #1

2
1 -2
4 5

样例输出 #1

4

样例 #2

样例输入 #2

3
1 2 3
4 5 6
7 8 9

样例输出 #2

0

样例 #3

样例输入 #3

3
-3 4 5
7 9 -2
1 0 -6

样例输出 #3

5

提示

【数据范围】

对于 $100\%$ 的数据，$1 \le N \le 400$，矩阵元素 $\in [-10^3,10^3]$。

【说明】

本题分值满分 $80$。