Untitled

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

class LocationInfo {
	boolean hasLake;
	boolean canExit;
	int numDiamond;

	public LocationInfo() {
		this.hasLake = false;
		this.canExit = false;
		this.numDiamond = 0;
	}

	public String toString() {
		String string = "0";
		if (hasLake)
			string = "2";
		if (canExit)
			string += ",3";
		string = string + ", " + numDiamond;
		return string;
	}

	public int takeTimeToMove() {
		if (hasLake)
			return 2;
		return 1;
	}
}

class FireInfo {
	int X;
	int Y;
	int timeFireSpread;

	public FireInfo(int _x, int _y, int _t) {
		this.X = _x;
		this.Y = _y;
		this.timeFireSpread = _t;
	}

	public String toString() {
		return "(" + X + "," + Y + ", " + timeFireSpread + ")";
	}
}

// FIFO
class HQueue {
	private Node head;
	private Node tail;
	private int size = 0;

	public HQueue() {
	}

	public int size() {
		return size;
	}

	public boolean isEmpty() {
		if (head == null)
			return true;
		return false;
	}

	public void enqueue(FireInfo data) {
		size++;
		if (head == null) {
			head = new Node(data, head);
			tail = head;
			return;
		}
		if (data.timeFireSpread < head.data.timeFireSpread) {
			head = new Node(data, head);
			return;
		}

		Node run = head;
		while (run.next != null) {
			if (run.data.timeFireSpread <= data.timeFireSpread
					&& data.timeFireSpread <= run.next.data.timeFireSpread) {
				break;
			}
			run = run.next;
		}
		if (run == tail) {
			tail.next = new Node(data);
			tail = tail.next;
		} else {
			Node newNode = new Node(data, run.next);
			run.next = newNode;
		}
	}

	public FireInfo dequeue() {
		if (head == null)
			throw new NullPointerException(
					"Queue is empty, so head value is null");
		else {
			size--;
			Node temp = head;
			head = head.next;
			temp.next = null;
			return (FireInfo) temp.data;
		}
	}

	public FireInfo top() {
		if (head == null)
			throw new NullPointerException(
					"Stack is empty, so head value is null");
		else {
			return (FireInfo) head.data;
		}
	}

	public void print() {
		System.out.print("{Queue}[");
		Node run = head;
		if (head == null) {
			System.out.println("]");
			return;
		}
		while (run.next != null) {
			System.out.print(run.data + "<=");
			run = run.next;
		}
		System.out.println(run.data + "]");
	}

	public void clear() {
		head = null;
		tail = head;
	}

	class Node {
		FireInfo data;
		Node next;

		public Node(FireInfo data) {
			this.data = data;
			this.next = null;
		}

		public Node(FireInfo data, Node next) {
			this.data = data;
			this.next = next;
		}
	}
}

public class Hugo {

	// 0: empty cell
	// 1: cell has fire
	// 2: cell has lake
	// 3: cell has exit

	private static LocationInfo[][] locationInfo;
	private static int[][] visited;
	private static int[][] timeFireSpread;

	private static int M, N, Xstart, Ystart;

	private static int maxAmountDiamond;

	private static int[] dx = { -1, 0, 1, 0 };
	private static int[] dy = { 0, 1, 0, -1 };

	private static void calculateTimeFire() {

		HQueue queue = new HQueue();
		for (int i = 0; i < M; i++) {
			for (int j = 0; j < N; j++) {
				if (timeFireSpread[i][j] == 0) {
					queue.enqueue(new FireInfo(i, j, 0));
				}
			}
		}

		while (!queue.isEmpty()) {
			FireInfo currFireInfo = queue.dequeue();

			for (int i = 0; i < 4; i++) {
				int Xc = currFireInfo.X + dx[i];
				int Yc = currFireInfo.Y + dy[i];

				if (Xc < 0 || Xc >= M)
					continue;
				if (Yc < 0 || Yc >= N)
					continue;

				if (timeFireSpread[Xc][Yc] == -1
						&& !locationInfo[Xc][Yc].hasLake) {
					timeFireSpread[Xc][Yc] = currFireInfo.timeFireSpread + 1;
					queue.enqueue(new FireInfo(Xc, Yc, timeFireSpread[Xc][Yc]));
				}
			}
		}
		// for (int i=0; i < M; i++) {
		// for (int j=0; j < N; j++) {
		// System.out.print(timeFireSpread[i][j] + "\t");
		// }
		// System.out.println();
		// }
	}

	public static void backtrack(int Xstart, int Ystart, int numDiamond,
			int timeTravel) {

		if (timeFireSpread[Xstart][Ystart] != -1
				&& timeTravel >= timeFireSpread[Xstart][Ystart]) {
			// System.out.println("DK 1");
			return;
		}
		if (locationInfo[Xstart][Ystart].canExit) {
			// System.out.println("DK dung: " + numDiamond);
			if (maxAmountDiamond < numDiamond)
				maxAmountDiamond = numDiamond;
		}

		for (int i = 0; i < dx.length; i++) {
			int Xc = Xstart + dx[i];
			int Yc = Ystart + dy[i];

			if (Xc < 0 || Xc >= M)
				continue;
			if (Yc < 0 || Yc >= N)
				continue;

			// System.out.println("Move to: " + Xc + ", " + Yc);

			if (visited[Xc][Yc] == 0) {
				visited[Xc][Yc] = 1;
				// System.out.println("Time: " + (timeTravel +
				// locationInfo[Xc][Yc].takeTimeToMove()));
				backtrack(Xc, Yc, numDiamond + locationInfo[Xc][Yc].numDiamond,
						timeTravel + locationInfo[Xc][Yc].takeTimeToMove());
				visited[Xc][Yc] = 0;
			}

		}

	}

	public static void main(String[] args) throws FileNotFoundException {
		 System.setIn(new FileInputStream("HugoFull"));
		Scanner sc = new Scanner(System.in);

		int num_tc = sc.nextInt();
		for (int tc = 1; tc <= num_tc; tc++) {
			M = sc.nextInt();
			N = sc.nextInt();
			Xstart = sc.nextInt() - 1;
			Ystart = sc.nextInt() - 1;

			locationInfo = new LocationInfo[M][N];
			visited = new int[M][N];
			timeFireSpread = new int[M][N];

			for (int i = 0; i < M; i++) {
				for (int j = 0; j < N; j++) {
					locationInfo[i][j] = new LocationInfo();
					visited[i][j] = 0;
					timeFireSpread[i][j] = -1;
				}
			}

			// store length of arrays
			int n;

			// read fires position
			n = sc.nextInt();
			for (int i = 0; i < n; i++) {
				int x = sc.nextInt() - 1;
				int y = sc.nextInt() - 1;
				timeFireSpread[x][y] = 0;
			}

			// read fires position
			n = sc.nextInt();
			for (int i = 0; i < n; i++) {
				int x = sc.nextInt() - 1;
				int y = sc.nextInt() - 1;
				locationInfo[x][y].hasLake = true;
			}

			// read fires position
			n = sc.nextInt();
			for (int i = 0; i < n; i++) {
				int x = sc.nextInt() - 1;
				int y = sc.nextInt() - 1;
				locationInfo[x][y].canExit = true;
			}

			for (int i = 0; i < M; i++) {
				for (int j = 0; j < N; j++) {
					locationInfo[i][j].numDiamond = sc.nextInt();
				}
			}

			// for (int i=0; i < M; i++) {
			// for (int j=0; j < N; j++) {
			// System.out.print(locationInfo[i][j] + "\t");
			// }
			// System.out.println();
			// }
			//
			maxAmountDiamond = Integer.MIN_VALUE;
			visited[Xstart][Ystart] = 1;

			calculateTimeFire();

			// System.out.println("Hava: " +
			// locationInfo[Xstart][Ystart].numDiamond);

			backtrack(Xstart, Ystart, locationInfo[Xstart][Ystart].numDiamond,
					0);
			maxAmountDiamond = maxAmountDiamond == Integer.MIN_VALUE ? -1
					: maxAmountDiamond;
			System.out.println("Case #" + tc + "\n" + maxAmountDiamond);
		}
	}
}