题目内容

一支考古队在古道中发现了一座被封印的宝箱。只有按照特定规则集齐若干文物碎片，宝箱才会打开。考古队需要在一片 $n \times m$ 的网格区域内行动。

每个格子中有一个整数，含义如下：0 表示可通行的空地；1 表示障碍物，不能进入或经过；2 表示起点；3 表示宝箱所在位置；4 到 9 表示文物碎片，该数字本身即为碎片编号。

考古队从起点出发，每次只能向上、下、左、右移动一格，不能斜向移动。每次移动耗时 1 单位时间。必须按照碎片编号从小到大的顺序收集所有碎片，最后到达宝箱。如果存在多条可行路线，需要选择总耗时最短的路线。

收集时还需满足以下规则：

• 碎片编号必须按升序处理：先收集完当前编号的所有碎片，再收集下一个编号的碎片。
• 同一编号的碎片可能出现多次，每一块都必须被收集。对于同一编号的多个碎片，收集顺序可以任意选择。
• 除障碍物 1 外，其余格子（包括起点、宝箱和碎片所在格子）均可通行。

约束条件：

• 网格行数 $n$ 和列数 $m$ 均不超过 20。
• 同一编号碎片的出现次数不超过 3。
• 保证至少存在一条满足上述规则的有效路径。

输入描述

第一行包含两个整数 n 和 m，分别表示网格的行数和列数。

接下来 n 行，每行包含 m 个整数，依次表示该行每个格子的状态。

输出描述

输出一个整数，表示从起点出发，按编号升序收集完所有碎片并到达宝箱的最短总耗时。

样例1

输入

1 3
2 4 3

输出

2

说明

网格只有 1 行 3 列。起点在 $(0,0)$，编号 4 的碎片在 $(0,1)$，宝箱在 $(0,2)$。

依次经过起点、碎片、宝箱，共移动 2 步，所以输出 2。

样例2

输入

3 3
2 0 4
0 1 0
6 0 3

输出

8

说明

网格中出现了编号 4 和编号 6 的碎片，编号 5 没有出现，因此收集顺序为 4 后直接收集 6。

起点到编号 4 的最短距离为 2。编号 4 到编号 6 的最短距离为 4，需要绕过中间的障碍物。编号 6 到宝箱的最短距离为 2。

总耗时为 $2+4+2=8$，输出 8。

样例3

输入

4 3
2 0 0
4 1 4
0 5 0
0 0 3

输出

9

说明

网格中有两个编号 4 的碎片，分别位于 $(1,0)$ 和 $(1,2)$；编号 5 的碎片位于 $(2,1)$，宝箱位于 $(3,2)$。

两个编号 4 的碎片可以按任意顺序收集。若先收集 $(1,0)$，再收集 $(1,2)$，则距离依次为：起点到第一个 4 是 1，两个 4 之间是 4，第二个 4 到编号 5 是 2，编号 5 到宝箱是 2。

总耗时为 $1+4+2+2=9$。若先收集 $(1,2)$，结果为 $3+4+2+2=11$，更长，因此最短耗时为 9。