matteg.cpp

#include <bits/stdc++.h>
#define MAXN 2005000
#define ii pair <int, int>
#define ll long long
#define ff first
#define ss second
using namespace std;


int dp[MAXN];
int r, c;
int pot[11], ma[2000][2000];

ii finalPos[MAXN];
ii neutro = {1e9, 1e9};
ii sinais[5] = {{0, 0}, {1, 1}, {-1, 1}, {1, -1}, {-1, -1}};
ii start;
vector <ii> pares;

int bit(int num, int idx) {
	return (num / pot[idx]) % 5;
}

inline bool valido (ii pos) {
	return pos.ff >= 0 && pos.ff < r && pos.ss >= 0 && pos.ss < c;
}

int solve(int mask) {
	if (dp[mask] != -1) return dp[mask];
	
	ii atual = finalPos[mask];

	int res = 0;
	for (int i=0; i<((int) pares.size()); i++) {
		if (bit(mask, i) == 0) {
			for (int j=1; j<=4; j++){
				int newMask = mask + (pot[i] * j);
				if (valido(finalPos[newMask]))
					res = max(res, solve(newMask));
			}
		}
	}

	return dp[mask] = res + ma[atual.ff][atual.ss];
}


int main(){
	#ifdef LOCAL
	freopen("input", "r", stdin);
	#endif

	for (int i = 0, base = 1; i<10; i++, base *= 5){
		pot[i] = base;
	}

	int t, m;
	scanf("%d", &t);

	while (t--){
		scanf("%d", &r);
		scanf("%d", &c);
		scanf("%d", &m);

		pares.clear();

		scanf("%d", &start.ff);
		scanf("%d", &start.ss);


		int x, y;
		for (int i=0; i<m; i++) {
			scanf("%d", &x);
			pares.emplace_back(x, 0);
		}

		for (int i=0; i<m; i++){
			scanf("%d", &y);
			pares[i].ss = y;
		}
		
		for (int num=0; num<pot[m]; num++) {
			dp[num] = -1;
			finalPos[num] = start;
			for (int i=0; i<m; i++) {
				ii sinal = sinais[bit(num, i)];
				finalPos[num].ff += pares[i].ff * sinal.ff;
				finalPos[num].ss += pares[i].ss * sinal.ss;
			}
		}


		int inp;
		for (int i=0; i<r; i++) {
			for (int j=0; j<c; j++) {
				scanf("%d", &inp);
				ma[i][j] = inp;
			}
		}

		printf("%d\n", solve(0));
	}

	return 0;
}