数字方格

题目描述

给你一个正整数 $N$。

我们有一个 $N$ 行 $N$ 列的网格,从上数第 $i$ 行、从左数第 $j$ 列的格子写有数字 $A_{i,j}$。

假设这个网格的上边与下边相连,左边与右边相连。也就是说,以下所有结论成立。

$(N,i)$ 紧挨在 $(1,i)$ 的上方,$(1,i)$ 紧挨在 $(N,i)$ 的下方。$(1\le i\le N)$。

$(i,N)$ 紧挨在 $(i,1)$ 的左边,$(i,1)$ 紧挨在 $(i,N)$ 的右边。$(1\le i\le N)$。

高桥君将先从以下八个方向中选择一个:上、下、左、右以及四个对角线方向。然后,他选择任意一个格子作为起点,并沿所选方向每次移动一格,重复 $N-1$ 次。

在这个过程中,高桥君经过 $N$ 个格子。求将高桥君经过的格子上的数字按访问顺序从左到右排列得到的整数的最大可能值。

输入格式

输入按以下格式从标准输入给出:

N
A_{1,1}A_{1,2}… A_{1,N}
A_{2,1}A_{2,2}… A_{2,N}
⋮
A_{N,1}A_{N,2}… A_{N,N}

输出格式

输出答案。

样例

4
1161
1119
7111
1811

9786

如果高桥君从从上数第 $2$ 行、从左数第 $4$ 列的格子出发,沿右下方向移动,则经过的格子上的数字排列得到的整数为 $9786$。

不可能得到比 $9786$ 更大的值,因此答案是 $9786$。

10
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111

1111111111

注意答案可能超出 32 位整数的范围。

数据范围

• $1 \le N \le 10$
• $1 \le A_{i,j} \le 9$
• 输入中的所有值均为整数。