Hugo

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Hugo {
	static int N, M;
	static int MoveX[] = { 0, 0, 1, -1 };
	static int MoveY[] = { 1, -1, 0, 0 };
	static int xHugo, yHugo;
	static int front, rear;
	static int result;
	private static int[][] Q = new int[2][1000000];
	private static int[][] Chay = new int[20][20];
	private static int[][] Ho = new int[20][20];
	private static int[][] Thoat = new int[20][20];
	private static int[][] KC = new int[20][20];
	private static int[][] VS = new int[20][20];

	public static void main(String[] args) throws FileNotFoundException {
		// TODO Auto-generated method stub
		System.setIn(new FileInputStream("input.txt"));
		Scanner sc = new Scanner(System.in);
		int T;
		T = sc.nextInt();
		for (int test_case = 1; test_case <= T; test_case++) {
			System.out.println("Case #" + test_case);
			N = sc.nextInt();
			M = sc.nextInt();
			N++;
			M++;
			xHugo = sc.nextInt();
			yHugo = sc.nextInt();
			reset();
			int n, x, y;
			n = sc.nextInt(); // input chay
			for (int i = 0; i < n; i++) {
				x = sc.nextInt();
				y = sc.nextInt();
				Chay[x][y] = 0;
				rear++;
				Q[0][rear] = x;
				Q[1][rear] = y;
			}
			n = sc.nextInt();// input ho
			for (int i = 0; i < n; i++) {
				x = sc.nextInt();
				y = sc.nextInt();
				Ho[x][y] = 1;
			}

			n = sc.nextInt();// input thoat
			for (int i = 0; i < n; i++) {
				x = sc.nextInt();
				y = sc.nextInt();
				Thoat[x][y] = 1;
			}

			// input kim cuong
			for (int i = 1; i < N; i++) {
				for (int j = 1; j < M; j++) {
					KC[i][j] = sc.nextInt();
					;
				}
			}

			BFS_Chay();
			VS[xHugo][yHugo] = 1;
			BT_Hugo(xHugo, yHugo, 0, KC[xHugo][yHugo]);

			System.out.println(result);
		}
	}

	static void reset() {
		for (int i = 0; i < 20; i++) {
			for (int j = 0; j < 20; j++) {
				Chay[i][j] = 1000000;
				Ho[i][j] = -1;
				Thoat[i][j] = -1;
				KC[i][j] = 0;
				VS[i][j] = -1;
			}
		}
		front = -1;
		rear = -1;
		result = -1;
	}

	static void BFS_Chay() {
		while (front < rear) {
			front++;
			int x = Q[0][front];
			int y = Q[1][front];
			for (int i = 0; i < 4; i++) {
				int xn = x + MoveX[i];
				int yn = y + MoveY[i];
				if (xn > 0 && xn < N && yn > 0 && yn < M
						&& Chay[xn][yn] == 1000000 && Ho[xn][yn] == -1) {
					Chay[xn][yn] = Chay[x][y] + 1;
					rear++;
					Q[0][rear] = xn;
					Q[1][rear] = yn;
				}
			}
		}
	}

	static void BT_Hugo(int x, int y, int t, int kc) {
		if (Thoat[x][y] == 1) {
			result = kc > result ? kc : result;
		}
		for (int i = 0; i < 4; i++) {
			int xn = x + MoveX[i];
			int yn = y + MoveY[i];
			if (xn > 0 && xn < N && yn > 0 && yn < M && VS[xn][yn] == -1) {
				if (Ho[xn][yn] == 1) {
					VS[xn][yn] = 1;
					BT_Hugo(xn, yn, t + 2, kc + KC[xn][yn]);
					VS[xn][yn] = -1;
				} else if (Ho[xn][yn] == -1 && t + 1 < Chay[xn][yn]) {
					VS[xn][yn] = 1;
					BT_Hugo(xn, yn, t + 1, kc + KC[xn][yn]);
					VS[xn][yn] = -1;
				}
			}
		}
	}

}