Background

这次小偷来到了一个迷宫，眼看小偷就要被神探抓住了，没想要狡猾小偷在迷宫里安装了一个 C4，这个 C4马上就要爆炸了！！！他们现在都在迷宫的中间，神探必须以最快的速度赶往出口（入口和出口都是可以的）。

Description

输入一个奇数 $n(0\le n\le10)$ 表示这个迷宫有 $n*n$ 这么大，迷宫的左上角和右下角都可以出去，现在神探在正中间，也就是中间的点标记为 $0$。其他的点上都为一个数字，表示到这个点需要的时间。问神探最少要多少秒才能从迷宫出去。

Format

Input

一个整数 $n$ 表示迷宫有 $n*n$ 这么大，接下来有 $n$ 行 $n$ 列，表示这个迷宫。

Output

神探最少要多少秒才能从迷宫出去

Samples

3 
1 2 3
5 0 3
1 2 4

3