Untitled

#include <iostream>
using namespace std;

int m, n, sr, sc, a[17][17], k, h, out, res;
int s[16][16];
int thoat[16][16];
bool ho[16][16];
bool vt[16][16];
int rspin[] = {0, -1, 1, 0};
int cspin[] = {1, 0, 0, -1};
const int MAX_SIZE = 100000;

struct Point {
	int x, y;
};

template <typename T>
class Queue {
	int front, rear;
	T data[MAX_SIZE];
public:
	Queue() {
		front = rear = -1;
	}
	bool isFull() {
		return (front == 0 && rear == MAX_SIZE-1) || (front == rear + 1);
	}
	bool isEmpty() {
		return front == -1;
	}
	void reset() {
		front = rear = -1;
	}
	void enQueue(T val) {
		if (!isFull()) {
			if (front == -1)	front++;
			rear = (rear + 1) % MAX_SIZE;
			data[rear] = val;
		}
	}
	T deQueue() {
		if (!isEmpty()) {
			T element = data[front];
			if (front == rear) {
				reset();
			} else {
				front = (front + 1) % MAX_SIZE;
			}
			return element;
		}
	}
};

void resetVisit() {
	for(int i = 0; i <= m; i++) {
		for(int j = 0; j <= n; j++) {
			vt[i][j] = false;
		}
	}
}

void reset() {
	for(int i = 0; i <= m; i++) {
		for(int j = 0; j <= n; j++) {
			s[i][j] = 0;
			thoat[i][j] = 0;
			ho[i][j] = false;
		}
	}
}

Queue<Point> q;


void BFS() {
	while(!q.isEmpty()) {
		Point cur = q.deQueue();
		for(int i = 0; i < 4; i++) {
			int x = cur.x + rspin[i];
			int y = cur.y + cspin[i];
			if (x > 0 && y > 0 && x <= m && y <= n && !vt[x][y] && s[x][y] == 0) {
				Point next = {x, y};
				s[x][y] = s[cur.x][cur.y] + 1;
				q.enQueue(next);
				vt[x][y] = true;
			}
		}
	}

	for(int i = 1; i <= m; i++) {
		for(int j = 1; j <= n; j++) {
			if (s[i][j] == 0) {
				s[i][j] = -1;
			} else {
				s[i][j] -= 1;
			}

		}
	}
}

void backtrack(int r, int c, int status, int score) {
	if (thoat[r][c] == 1) {
		if (score > res)	res = score;
	}
	for(int i = 0; i < 4; i++) {
		int x = r + rspin[i];
		int y = c + cspin[i];
		int nextTime = status + 1;
		if (ho[r][c])	nextTime = status + 2;
		if (x > 0 && y > 0 && x <= m && y <= n && !vt[x][y] && (s[x][y] > nextTime || s[x][y] < 0)) {
			vt[x][y] = true;
			backtrack(x, y, nextTime, score + a[x][y]);
			vt[x][y] = false;
		}
	}
}

void solve(int index) {
	reset();
	resetVisit();
	res = 0;
	cin>>m>>n>>sr>>sc;
	cin>>k;
	int x, y;
	q.reset();
	for(int i = 1; i <= k; i++) {
		cin>>x>>y;
		s[x][y] = 1;
		Point tmp = {x, y};
		q.enQueue(tmp);
	}
	cin>>h;
	for(int i = 1; i <= h; i++) {
		cin>>x>>y;
		s[x][y] = 1000000;
		ho[x][y] = true;
	}
	cin>>out;
	for(int i = 1; i <= out; i++) {
		cin>>x>>y;
		thoat[x][y] = 1;
	}
	for(int i = 1; i <= m; i++) {
		for(int j = 1; j <= n; j++) {
			cin>>a[i][j];
		}
	}
	BFS();
	resetVisit();
	vt[sr][sc] = true;
	backtrack(sr, sc, 0, a[sr][sc]);
	if (res == 0) {
		cout<<"Case #"<<index<<endl;
		cout<<-1<<endl;
	} else {
		cout<<"Case #"<<index<<endl;
		cout<<res<<endl;
	}
}

int main() {
	freopen("input.txt", "r", stdin);
	int t;
	cin>>t;
	for(int i = 1; i <= t; i++) {
		solve(i);
	}
	return 0;
}