Problem Statement

There is a grid with $H$ rows and $W$ columns. The cell in the $i$-th row from the top and the $j$-th column from the left is denoted by $(i,j)$.
Cell $(i,j)$ has a non-negative integer $A_{i,j}$ written on it, and these integers are pairwise distinct.
Initially, $(1,1)$ is painted with color $1$ and $(H,W)$ is painted with color $0$, and no other cell is painted with any color.

Perform the following operation as long as there is no place where a cell painted with color $1$ and a cell painted with color $0$ are adjacent. Here, $2$ cells $(i_1, j_1), (i_2, j_2)$ are said to be "adjacent" if and only if $ |i_1-i_2| + |j_1-j_2| = 1$.

• In the $i$-th operation, among the unpainted cells adjacent to a cell painted with color $i \bmod 2$, paint the cell with the smallest written number with color $i \bmod 2$.

Input

$H\ W$
$A_{1, 1}\ A_{1, 2}\ \cdots\ A_{1, W}$  
$A_{2, 1}\ A_{2, 2}\ \cdots\ A_{2, W}$  
$\vdots$  
$A_{H, 1}\ A_{H, 2}\ \cdots\ A_{H, W}$  

• All input values are integers.
• $2 \leqq H, W \leqq 10^3$
• $1 \leqq A_{i,j} \leqq 10^9$
• All $A_{i,j}$ are distinct.

Output

Output the answer.

Sample

Sample 1

Input

3 3
1 2 3
7 6 8
9 5 4

Output

4

The operations are performed as follows. (In the figure, red represents color $1$ and blue represents color $0$.)

5 4
1 10 1000 100
200 2 20 2000
3 30 300 3000
4 40 4000 400
500 50 5000 5

6

5 5
1 2 101 102 103
4 3 104 105 106
107 108 109 110 111
112 113 114 7 8
115 116 117 6 5

10