問題文

縦 $H$ 行、横 $W$ 列のグリッドがあります。上から $i$ 行目、左から $j$ 列目のマスを $(i,j)$ で表します。
マス $(i,j)$ には互いに異なる非負整数 $A_{i,j}$ が書かれています。
初め、$(1,1)$ に色 $1$、$(H,W)$に色 $0$ が塗られており、その他のマスは何も色が塗られていません。

以下の操作を色 $1$ が塗られたマスと色 $0$ が塗られたマスが隣接している箇所が存在しない間行います。なお、$2$ つのマス$(i_1, j_1), (i_2, j_2)$ は $|i_1-i_2| + |j_1-j_2| = 1$を満たすとき、またその時に限り「隣接している」といいます。

• $i$ 回目の操作の時、色 $i \bmod 2$ が塗られたマスと隣接している何も塗られていないマスのうち、書かれている数字が最も小さいマスに色 $i \bmod 2$ を塗る。

入力

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

• 入力はすべて整数
• $2 \leqq H, W \leqq 10^3$
• $1 \leqq A_{i,j} \leqq 10^9$
• $A_{i,j}$ はすべて異なる。

出力

答えを出力してください。

サンプル

サンプル1

入力サンプルをコピー

入力

3 3
1 2 3
7 6 8
9 5 4

出力

4

以下のように操作が行われます。(図では赤は色 $1$、青は色 $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