题目描述

有一个 $N \times N$ 的矩阵，找出它的美丽值最大的子矩阵，要求这个子矩阵是正方形，即长和宽相等。

定义一个矩阵的美丽值为：将这个矩阵主对角线上的数的和定义为 $A$，另一条对角线上的数的和定义为 $B$，则这个矩阵的美丽值为 $A - B$。

输入格式

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

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

输出格式

输出一行一个整数，表示最大的美丽值。

2
1 -2
4 5

4

3
1 2 3
4 5 6
7 8 9

0

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

5

提示

【数据范围】

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

【说明】

本题分值按 COCI 原题设置，满分 $80$。

题目译自 COCI2011-2012 CONTEST #1 T2 MATRIX。