问题文

给定一个大小为 $H$ 行 $W$ 列的滑块谜题棋盘（如图1所示）。

图1. 滑块谜题棋盘

每个格子上标有从 $1$ 到 $H×W-1$ 的不同数字，其中一个格子为空。

在这个滑块谜题中，你可以将空白格子与左右上下相邻的格子交换位置。但是，如果要交换的方向没有格子存在，则不能进行交换。

你想通过任意次数的交换操作将棋盘调整为完成状态。这里，完成状态表示从左上角开始按顺序标号，右下角是空白格子（如图2所示）。

图2. 完成盘面

换句话说，完成的盘面要满足：

• 编号为 $i (1≦i≦H×W-1)$ 的格子位于 (1+\[(i-1)÷W\],1+(i-1)%W)
• 空白格子位于 $(H,W)$

其中 \[a÷b\] 表示 $a$ 除以 $b$ 的结果向下取整，$a$ 表示 $a$ 除以 $b$ 的余数。

已保证最小操作次数不超过 $24$ 次。请输出解决谜题所需的最小操作次数。

---

输入

输入从标准输入中提供，具有以下格式：

$H$ $W$ $c_{1,1}$ $c_{1,2}$ … $c_{1,W}$ $c_{2,1}$ $c_{2,2}$ … $c_{2,W}$ : $c_{H,1}$ $c_{H,2}$ … $c_{H,W}$

• 第一行包含两个用空格分隔的整数，分别表示滑块谜题棋盘的纵向长度 $H (2≦H≦6)$ 和横向长度 $W (2≦W≦6)$。
• 第二行到第 $H$ 行给出了棋盘的信息。其中第 $i (1≦i≦H)$ 行给出了滑块谜题棋盘坐标 $(i,1),(i,2),...,(i,W)$ 上的格子中的数字，用空格分隔的整数表示 $c_{i,1},c_{i,2},...,c_{i,W}$。其中，$c_{i,j}=0$ 表示该格子为空白格子。
• 棋盘保证出现恰好一个整数，范围从 $1$ 到 $H×W-1$，和一个表示空白格子的整数 $0$。
• 已保证解决谜题所需的最小操作次数不超过 $24$ 次。

输出

输出一行，包含解决谜题所需的最小操作次数。不要忘记结束时的换行符。

---

输入例子1

3 3
1 0 2
4 5 3
7 8 6

输出例子1

3

起初，空白格子位于 $(1,2)$。通过将空白格子移动为 "右→下→下"，可以达到完成状态，并且此时达到了最小操作次数。

---

输入例子2

3 5
6 1 2 8 5
7 0 4 3 10
11 12 13 9 14

输出例子2

12

---

输入例子3

2 2
1 2
3 0

输出例子3

0

---

输入例子4

4 4
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 0

输出例子4

0

滑块已经处于完成状态。

---

输入例子5

6 6
1 2 3 4 5 6
14 15 10 16 11 12
8 9 19 17 0 18
7 13 20 22 23 24
25 26 21 28 29 30
31 32 27 33 34 35

输出例子5

24

这是输出答案最大的情况。