#5070. 危险的迷宫

内存限制:256 MiB 时间限制:20 Sec

输入格式

第一行是两个整数A与B(1≤A,B≤10),中间用空格分隔,表示该迷宫是A行B列的。
第2行至第A+1行,每行有B个1至100以内的整数,表示该迷宫每一格的危险程度。
以下一行是一个整数K。接着K行每行有四个整数X0,Y0,X1,Y1,
(1 ≤X0,X1≤A, 1≤Y0,Y1≤B) ,(X0,Y0),(X1,Y1)为相邻的两格,这两格相通。
接着一行是一个整数N(0≤N≤A*B/2),表示有N个出口与入口。
以下N行,每行有两个整数X0,Y0,表示每个入口的行列位置。
以下还有N行,每行有两个整数X1,Y1,表示每个出口的行列位置。

输出格式

输出仅一个数,若队员们不能全部到达指定目标位置,则输出-1;
否则输出所有队员所经过的所有单元格的危险程度之和。

样例

样例输入


			
3 4
20 30 40 30
30 60 20 20
20 15 20 20
13
1 1 2 1
1 2 1 3
1 2 2 2
1 3 1 4
1 4 2 4
2 1 2 2
2 1 3 1
2 2 2 3
2 3 2 4
2 4 3 4
3 1 3 2
3 2 3 3
3 3 3 4
2
1 1
1 2
2 3
3 4

样例输出


			
235

数据范围与提示