Background

Special for beginners, ^_^

Description

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

活动区域：

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

方向：

对于P=(X ~0~ ,Y ~0~ )、Q=(X ~1~ ,Y ~1~ )，有以下四种基本方向：

l 正左(L)：X ~0~ =X~1~且Y ~0~ =Y ~1~ -1，则称P位于Q的正左方向。

l 正右(R)：X ~0~ =X~1~且Y ~0~ =Y ~1~ +1，则称P位于Q的正右方向。

l 正上(U)：X ~0~ =X ~1~ -1且Y ~0~ =Y~1~，则称P位于Q的正上方向。

l 正下(D)：X ~0~ =X ~1~ +1且Y ~0~ =Y~1~，则称P位于Q的正下方向。

贪食蛇：

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

l 对于B~i~和B ~i+1~ (1<=i<m)，就是贪食蛇的前、后相邻两部分，必须满足B~i~位于B~i+1~的L、R、U、D四个方向之一。

l 对于B~i~和B ~j~ (1<=i<j<=m)，p(B ~i~ )=(X ~i~ ,Y ~i~ )，p(B ~j~ )=(X ~j~ ,Y ~j~ )，需要满足X ~i~ !=X~j~或Y ~i~ !=Y~j~。也就是说，贪食蛇身体的任意一部分不能相交。

食物：

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

贪食蛇的运动：

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

l p’(B ~k~ )=p(B ~k-1~ )，当2<=k<=m。

l p’(B ~k~ )=(i,j)，当k=1

贪食蛇的进食：

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

l p’(B ~k~ )=p(B ~k-1~ )，当2<=k<=m’。

l p’(B ~k~ )=(i,j)，当k=1

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

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

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

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

Format

Input

第一行，两个正整数R、C。

接下来R行，每行C个没有空格分隔的数字。其中第i行第j个数字为w(A ~ij~ )。

接下来4行，每行2个正整数。第i行的两个整数X~i~、Y~i~，表示p(B ~i~ )=(X ~i~ ,Y ~i~ )。

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

接下来N行，每行2个正整数i、j，表示A~ij~上存在一个食物。

Output

如果贪食蛇不能吃到所有的食物，输出“No solution.”（不包括引号）。

否则，输出：

第一行，一个整数，表示所需花费的时间；

Samples

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

Limitation

对于20%的数据，N <= 1。

对于40%的数据，N <= 2。

对于60%的数据，N <= 3。

对于100%的数据，N <= 4。

对于30%的数据，R * C <= 36。

对于100%的数据，R <= 12，C <= 12。