C0923 [SDOI2011]贪食蛇

相信大家都玩过贪食蛇游戏，现在有一个改版贪食蛇游戏，跟传统的贪食蛇游戏一样，贪食蛇在活动区域内运动，吃食物，但是这个改版的贪食蛇游戏有着一些特别的规则。

活动区域：

贪食蛇的活动区域是一个 $R$ 行 $C$ 列的网格 $A$，贪食蛇活动不能超过这个网格的范围。第 $i$ 行第 $j$ 列的方格用 $A_{i,j}$表示。每个方格有一个整数权值，记作 $w(A_{ij})$。$0 \le w(A_{ij}) \le 8$，$w(A_{ij})=0$ 时，$A_{ij}$ 禁止进入；$w(A_{ij})>0$ 时，$A_{ij}$ 允许进入。

方向：

对于 $P=(X_0,Y_0)$、$Q=(X_1,Y_1)$，有以下四种基本方向：

• 正左(L)：$X_0=X_1$ 且 $Y_0=Y_{1-1}$，则称 $P$ 位于 $Q$的正左方向。

• 正右(R)：$X_0=X_1$ 且 $Y_0=Y_{1+1}$，则称 $P$ 位于 $Q$ 的正右方向。

• 正上(U)：$X_0=X_{1-1}$ 且 $Y_0=Y_1$，则称 $P$ 位于 $Q$ 的正上方向。

• 正下(D)：$X_0=X_{1+1}$ 且 $Y_0=Y_1$，则称 $P$ 位于 $Q$ 的正下方向。

贪食蛇：

贪食蛇 $B$ 是占据若干方格的图形，占据的方格数为贪食蛇的长度，记为 $m$，则贪食蛇从头到尾，用 $B_1$、$B_2$、……、$B_m$ 表示。记 $p$ 为贪食蛇的形态，若 $B_i$ 位于第 $X_i$ 行第 $Y_i$ 列，则 $p(B_i)=(X_i,Y_i)$。初始情况下，$m=4$，且运动过程中始终需要满足以下限制：

• 对于 $B_i$ 和 $B_{i+1}(1 \le i<m)$，就是贪食蛇的前、后相邻两部分，必须满足 $B_i$ 位于 $B_{i+1}$ 的L、R、U、D四个方向之一。

• 对于 $B_i$ 和 $B_j(1\le i<j \le m)$，$p(B_i)=(X_i,Y_i)$，$p(B_j)=(X_j,Y_j)$，需要满足 $X_i \ne X_j$ 或 $Y_i \le Y_j$。也就是说，贪食蛇身体的任意一部分不能相交。

食物：

贪食蛇的活动区域内存在一些食物。每个食物位于一个允许进入的方格上，食物不会重叠。每个食物只能被吃一次。

贪食蛇的运动：

如果贪食蛇的头部 $B_1$ 的L、R、U、D四个方向之一的 $A_{ij}$ 能进入，且 $A_{ij}$ 上不存在食物，则贪食蛇可以向该方向运动，新的头部位于 $A_{ij}$ 上。记 $p'$ 为贪食蛇新的形态，则：

• $p'(B_k)=p(B_{k-1})$，当 $2 \le k \le m$。

• $p'(B_k)=(i,j)$，当 $k=1$

贪食蛇的进食：

如果贪食蛇的头部 $B_1$ 的L、R、U、D四个方向之一的 $A_{ij}$ 能进入，且 $A_{ij}$ 上存在食物，则贪食蛇可以向该方向进食，新的头部位于 $A_{ij}$ 上，蛇的新长度 $m'=m+1$。记 $p'$ 为贪食蛇新的位置，则：

• $p'(B_k)=p(B_{k-1})$，当 $2 \le k \le m'$。

• $p'(B_k)=(i,j)$，当 $k=1$

注意：运动或进食后的贪食蛇形态，仅仅需要考虑变换后的形态是否满足限制，不需要考虑变换的过程。也就是说，原来形态合法的贪食蛇的头部可以运动到尾部的位置，因为在变换后头部和尾部仍不会重叠。

运动或进食所需要的时间：

贪食蛇运动或进食，需要消耗时间。设运动或进食前头部所在的方格是 $P$，运动或进食后头部所在的方格是 $Q$，则此次运动或进食的所消耗的时间为 $|w(P)-w(Q)|+1$。

游戏的会在开始前给出贪食蛇的初始位置和所有食物的位置。你的任务是，以最少的时间令贪食蛇吃完所有食物。

样例输入 1

5 5
11011
11011
11011
11011
11411
1 1
2 1
3 1
4 1
4
5 5
4 4
2 5
1 4

样例输出 1

21