配点 : $200$ 点

問題文

正整数 $N$ が与えられます。

$N$ 行 $N$ 列のマス目があり、上から $i$ 行目、左から $j$ 列目のマスには数字 $A_{i,j}$ が書かれています。

このマス目は上下および左右がつながっているものとします。つまり以下が全て成り立ちます。

• $(1,i)$ の上のマスは $(N,i)$ であり、$(N,i)$ の下のマスは $(1,i)$ である。$(1\le i\le N)$
• $(i,1)$ の左のマスは $(i,N)$ であり、$(i,N)$ の右のマスは $(i,1)$ である。$(1\le i\le N)$

高橋君は、上下左右および斜めの $8$ 方向のうちいずれかを初めに選びます。そして、好きなマスから決めた方向に $1$ マス移動することを $N-1$ 回繰り返します。

高橋君は $N$ 個のマス上を移動することになりますが、高橋君が通ったマスに書かれている数字を左から通った順番に並べた整数としてあり得る最大のものを求めてください。

制約

• $1 \le N \le 10$
• $1 \le A_{i,j} \le 9$
• 入力はすべて整数。

入力

入力は以下の形式で標準入力から与えられる。

$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}$

出力

答えを出力せよ。

4
1161
1119
7111
1811

9786

高橋君が上から $2$ 行目、左から $4$ 列目のマスから出発し、右下に進むことで、通ったマスに書かれた数字を並べ $9786$ を作ることができます。 $9786$ より大きい値を作ることはできないため、$9786$ が解です。

10
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111

1111111111

32bit整数型に答えが収まるとは限らないことに注意してください。