题目描述

有一个 $N \times 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]$。