题目描述

给你一个正整数 $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$

接下来 $N$ 行每行 $N$ 个数字，注意数字之间没有用空格隔开，请选择合适的类型作为输入。

输出格式

输出一个整数代表答案

4
1161
1119
7111
1811

9786

10
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111

1111111111

提示

• $1\ \le\ N\ \le\ 10$
• $1\ \le\ A_{i,j}\ \le\ 9$

样例 1 解释

如果高桥从从上数第 $2$ 行，从左数第 $4$ 列的方格开始，向下向右排列，那么把写在被访问方格上的数字排列起来得到的整数是 $9786$ 。不可能得到大于 $9786$ 的值，所以答案是 $9786$ 。