Untitled

#include <iostream>
#define N 20
#define oo 2000000009
using namespace std;
int n,m,sr,sc;
//dam chay
int k;
//ho
int ho;
//thoat
int ex;
int a[20][20];
bool h[20][20];
bool thoat[20][20];
bool chay[N][N];
int vs[N][N],kc[N][N];
int dd[N][N];
int ans;
int min(int u, int v)
{
	if(u>v)return v;
	return u;
}
int max(int u, int v)
{
	if(u>v)return u;
	return v;
}

void doc()
{
	ans=-1;
	int u,v;
	cin>>n>>m>>sr>>sc;
	
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			{
				a[i][j]=0;
				dd[i][j]=0;
				kc[i][j]=oo;
				thoat[i][j]=chay[i][j]=h[i][j]=false;
		}
	cin>>k;
	for(int i=1;i<=k;i++)
	{
		cin>>u>>v;
		chay[u][v]=true;
	}
	cin>>ho;
	
	for(int i=1;i<=ho;i++)
	{
		cin>>u>>v;
		h[u][v]=true;
	}

	cin>>ex;
	
	for(int i=1;i<=ex;i++)
	{
		cin>>u>>v;
		thoat[u][v]=true;
	}

	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)cin>>a[i][j];
}
int sx[N*N],sy[N*N];
int hx[]={0,-1,0,1};
int hy[]={-1,0,1,0};
void bfs(int u,int v)
{
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)vs[i][j]=0;
	int dau=1,cuoi=0;
	vs[u][v]=1;
	sx[++cuoi]=u;
	sy[cuoi]=v;
	while(dau<=cuoi)
	{
		u=sx[dau];
		v=sy[dau];
		//cout<<u<<" "<<v<<"\n";
		dau++;
		for(int i=0;i<4;i++)
		{
			int xx=u+hx[i];
			int yy=v+hy[i];
			if(xx>0&&xx<=n&&yy>0&&yy<=m&&vs[xx][yy]==0&&h[xx][yy]!=true)
			{
				vs[xx][yy]=vs[u][v]+1;
				sx[++cuoi]=xx;
				sy[cuoi]=yy;
			}
		}
	}
}
void backtrack(int x, int y, int time, int sum)
{
	if(kc[x][y]<=time)return;
	if(thoat[x][y])
		{
			ans=max(ans,sum);
			//return;
	}
	for(int i=0;i<4;i++)
	{
		int u=x+hx[i];
		int v=y+hy[i];
		if(u>0 && u<=n && v>0 && v<=m)
		{
			int t;
			if(h[u][v])t=2;else t=1;
			if(kc[u][v]>time+t && dd[u][v]==0)
			{
				dd[u][v]=1;
				backtrack(u,v,time+t,sum+a[u][v]);
				dd[u][v]=0;
			}
		}
	}
	//return;
}
int main()
{
	//freopen("input.txt","r",stdin);
	int TC;
	cin>>TC;
	for(int tc =1;tc<=TC;tc++)
	{
		doc();
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++)if(chay[i][j])
			{
				bfs(i,j);
				for(int u=1;u<=n;u++)
					for(int v=1;v<=m;v++)if(vs[u][v])kc[u][v]=min(kc[u][v],vs[u][v]-1);
			}
		/*for(int i=1;i<=n;i++)
		{

			for(int j=1;j<=m;j++)cout<<kc[i][j]<<" ";
			cout<<"\n";
		}*/
		dd[sr][sc]=1;
		backtrack(sr,sc,0,a[sr][sc]);
		cout<<"Case #"<<tc<<"\n";
		cout<<ans<<"\n";
		
		
	}
	return 0;
}