题目描述

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

活动区域：

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

方向：

对于$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$ 是占据若干方格的图形，占据的方格数为贪食蛇的长度，记为 $l$，则贪食蛇从头到尾，用 $b_{1\cdots l}$ 表示。记 $p$ 为贪食蛇的形态，若 $b_i$ 位于第 $x_i$ 行第 $y_i$ 列，则 $p(b_i)=(x_i,y_i)$。初始情况下，$l=4$，且运动过程中始终需要满足以下限制：

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

• 对于 $b_i$ 和 $b_j(1 \leq i<j \leq l)$，$p(b_i)\not =p(b_j)$。也就是说，贪食蛇身体的任意一部分不能相交。

食物：

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

贪食蛇的运动：

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

• $p’(b_k)=p(b_{k-1})$，当 $2 \leq k \leq l$；

• $p’(b_k)=(i,j)$，当 $k=1$。

贪食蛇的进食：

如果贪食蛇的头部 $b_1$ 的 $L,R,U,D$ 四个方向之一的 $a_{i,j}$ 能进入，且 $a_{i,j}$ 上存在食物，则贪食蛇可以向该方向进食，新的头部位于 $a_{i,j}$ 上，蛇的新长度 $l‘=l+1$。记 $p’$ 为贪食蛇新的位置，则：

• $p’(b_k)=p(b_{k-1})$，当 $2 \leq k \leq l’$；

• $p’(b_k)=(i,j)$，当 $k=1$。

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

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

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

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

输入格式

第一行，两个正整数 $n,m$。

接下来 $n$ 行，每行 $m$ 个没有空格分隔的数字。其中第 $i$ 行第 $j$ 个数字为 $w(a_{i,j})$。

接下来四行，每行两个正整数。第 $i$ 行的两个整数 $x_i,y_i$，表示 $p(b_i)=(x_i,y_i)$。

接下来一个正整数 $k$，表示食物的数量。

接下来 $k$ 行，每行两个正整数 $i,j$，表示 $a_{i,j}$ 上存在一个食物。

输出格式

如果贪食蛇不能吃到所有的食物，输出 No solution.。

否则，输出一行一个整数，表示所需花费的时间。

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

21

数据规模与约定

对于 $100\%$ 的数据，$0 \leq w(a_{i,j}) \leq 8$，$1\leq n,m \leq 12$，$1\leq k\leq 4$。

对于 $20\%$ 的数据，$k \leq 1$。

对于 $30\%$ 的数据，$n \times m \leq 36$。

对于 $40\%$ 的数据，$k \leq 2$。

对于 $60\%$ 的数据，$k \leq 3$。