Untitled

package hugo;

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

public class Solution {
	static int n, m, sr, sc, lua, ho, lt, res;
	static int[][] kc, fire, visit, f, r, out;
	static int[] qx = new int[1005], qy = new int[1005], outx, outy;
	static int[] dx = { 0, 1, 0, -1 }, dy = { 1, 0, -1, 0 };
	static boolean checkout;

	// check bien
	public static boolean checkout(int x, int y) {
		if (x < 0 || y < 0 || x >= n || y >= m) {
			return false;
		}
		return true;
	}

	// lan lua -1 lua -2 ho
	public static void lanLua() {
		visit = new int[n][m];
		int front = 0, rear = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (fire[i][j] == -1) {
					qx[rear] = i;
					qy[rear] = j;
					visit[i][j] = 1;
					f[i][j] = 0;
					rear++;
				}
				if (fire[i][j] == -2) {
					f[i][j] = -2;
				}
			}
		}
		while (front < rear) {
			int x = qx[front], y = qy[front];
			int c = f[x][y];
			for (int i = 0; i < 4; i++) {
				int nx = x + dx[i], ny = y + dy[i];
				if (checkout(nx, ny) && fire[nx][ny] != -2) {
					if (visit[nx][ny] == 0) {
						qx[rear] = nx;
						qy[rear] = ny;
						f[nx][ny] = c + 1;
						visit[nx][ny] = 1;
						rear++;
					} else if (visit[nx][ny] == 1) {
						if (f[nx][ny] > c + 1) {
							qx[rear] = nx;
							qy[rear] = ny;
							f[nx][ny] = c + 1;
							rear++;
						}
					}
				}
			}

			front++;
		}
	}
	
	public static void updateLua(){
		for(int i = 0; i < n; i++){
			for(int j = 0; j < m; j++){
				if(f[i][j] == 0 && fire[i][j] == 0){
					f[i][j] = Integer.MAX_VALUE;
				}
			}
		}
	}
	
	
	public static void backTrack(int x, int y, int time, int count){
//		System.out.println(x + " - " + y + " " + time + " " + count);
		for (int i = 0; i < lt; i++) {
			if (x == outx[i] && y == outy[i]) {
				res = Math.max(res, count);
				checkout = true;
				break;
			}
		}
		for (int i = 0; i < 4; i++) {
			// System.out.println("for");
			int nx = x + dx[i], ny = y + dy[i];
			if (checkout(nx, ny) && visit[nx][ny] == 0 && fire[nx][ny] != -1) {
				if(fire[nx][ny] == 0 && time+1 < f[nx][ny]){
					visit[nx][ny] = 1;
					backTrack(nx, ny, time+1, count + kc[nx][ny]);
					visit[nx][ny] = 0;
				}else if(fire[nx][ny] == -2){
					visit[nx][ny] = 1;
					backTrack(nx, ny, time+2, count + kc[nx][ny]);
					visit[nx][ny] = 0;
				}
			}
		}
		
	}

	public static void main(String[] args) {
		try {
			System.setIn(new FileInputStream("input.txt"));
		} catch (FileNotFoundException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		Scanner scanner = new Scanner(System.in);
		int test = scanner.nextInt();
		for (int t = 1; t <= test; t++) {
			n = scanner.nextInt();
			m = scanner.nextInt();
			sr = scanner.nextInt() - 1;
			sc = scanner.nextInt() - 1;
			fire = new int[n][m];
			f = new int[n][m];
			r = new int[n][m];
			kc = new int[n][m];
			out = new int[n][m];
			lua = scanner.nextInt();
			for (int i = 0; i < lua; i++) {
				fire[scanner.nextInt() - 1][scanner.nextInt() - 1] = -1;
			}
			ho = scanner.nextInt();
			for (int i = 0; i < ho; i++) {
				fire[scanner.nextInt() - 1][scanner.nextInt() - 1] = -2;
			}
			lt = scanner.nextInt();
			outx = new int[lt];
			outy = new int[lt];
			for (int i = 0; i < lt; i++) {
				outx[i] = scanner.nextInt() - 1;
				outy[i] = scanner.nextInt() - 1;
				out[outx[i]][outy[i]] = 1;
			}
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < m; j++) {
					kc[i][j] = scanner.nextInt();
				}
			}
			

//			for (int i = 0; i < n; i++) {
//				for (int j = 0; j < m; j++) {
//					System.out.print(fire[i][j] + " ");
//				}
//				System.out.println();
//			}
//			System.out.println();

			lanLua();
			updateLua();
//			for (int i = 0; i < n; i++) {
//				for (int j = 0; j < m; j++) {
//					System.out.print(f[i][j] + " ");
//				}
//				System.out.println();
//			}
//			System.out.println();
//			
//			for (int i = 0; i < n; i++) {
//				for (int j = 0; j < m; j++) {
//					System.out.print(kc[i][j] + " ");
//				}
//				System.out.println();
//			}
//			System.out.println();
			
			out[sr][sc] = 2;
//			System.out.println();
//			for (int i = 0; i < n; i++) {
//				for (int j = 0; j < m; j++) {
//					System.out.print(out[i][j] + " ");
//				}
//				System.out.println();
//			}
//			System.out.println();

			
			res = 0; checkout = false;
			visit = new int[n][m];
			visit[sr][sc] = 1;
			backTrack(sr, sc, 0, kc[sr][sc]);
			
//			System.out.println(n + " " + m);
			if(checkout){
				System.out.println("Case #" + t + "\n" + res);
			}else{
				System.out.println("Case #" + t + "\n-1");
			}

		}
		scanner.close();
	}
}