题目描述

有一个 $N × N$ 的数字网格。方格的上下边缘和左右边缘是相连的。小高可以选择8个方向之一（上、下、左、右和四个对角线方向），从任意一个方格开始，沿着选定的方向移动$N-1$次。在这个过程中，小高会经过$N$个方格（包含起点格）。请找出通过将小高访问过的方格上的数字按照访问顺序从左到右排列所能得到的最大可能整数值。

输入格式

输入格式如下：

$N$

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

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

$\vdots$

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

输出格式

输出所求答案。

样例

4
1161
1119
7111
1811

9786

10
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111

1111111111

样例解释

【样例1说明】
如果小高从第2行第4列的方格开始，向右下方移动，得到的数字将是9786。不可能得到比9786更大的数字，所以答案是9786。
【样例2说明】
注意答案可能不适合32位整数。

数据范围

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

来源

• AtCoder ABC258B