题目描述

给定一个正整数 $N$ 和一个 $N \times N$ 的矩阵。

任意选定一个位置，向上、下、左、右、左上、右上、左下、右下， $8$ 个方向移动 $N - 1$ 次，使经过的数字拼凑起来最大。输出最大可能得到的数字。

这个矩阵是上下左右联通的，例如: $(i,N)$ 是在 $(i,1)$ 的左边，$(N,i)$ 是在 $(1,i)$ 的上面。 $(1 \le i \le N)$

输入格式

输入格式如下：

$N$

$A_{1,1}A_{1,2}\dots\ A_{1,N}$

$A_{2,1}A_{2,2}\dots\ A_{2,N}$

$\vdots$

$A_{N,1}A_{N,2}\dots\ A_{N,N}$

输出格式

输出所求答案。

样例 #1

样例输入 #1

4
1161
1119
7111
1811

样例输出 #1

9786

样例 #2

样例输入 #2

10
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111

样例输出 #2

1111111111

提示

样例说明 1

如果从第 2 行第 4 列的方格开始，向右下方移动，得到的数字将是 9786。不可能得到比 9786 更大的数字，所以答案是 9786。

样例说明 2

注意答案可能不适合 32 位整数。

数据范围

• $1\ \le\ N\ \le\ 10$
• $1\ \le\ A_{i,j}\ \le\ 9$
• 所有输入都是整数。