【题目描述】

给定一个 $n\times n$ 整数方阵。

可以选择任意一行、任意一列，或任意一条与主对角线或副对角线平行且经过至少一个格子的直线。

请输出所经过数字之和的最大值。

【输入描述】

第一行输入整数 $n$。

接下来 $n$ 行输入方阵。

保证：

• $1\le n\le 100$；
• $-10^5\le A_{i,j}\le 10^5$。

【输出描述】

输出一个整数，表示最大的数字之和。

【样例 1】

【样例 1 输入】

3
1 2 3
3 3 3
-5 1 2

【样例 1 输出】

9

【样例 1 解释】

第二行的和为 $3+3+3=9$，也是所有行、列以及两类平行对角线中的最大值。

【样例 2】

【样例 2 输入】

2
4 -100
-100 9

【样例 2 输出】

13