#include <iostream>#include <queue>#include <cstdio>#include <cstring>using namespace std;const int maxn=55;const int INF=1e8;struct node{ int x,y; int num;};int vis[maxn][maxn];int n,m,t,l,ans,sum;int val[11];int path[12][12],mark[12];int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};char e[maxn][maxn];void bfs(int x,int y,int from){ memset(vis,0,sizeof(vis)); vis[x][y]=1; int i,j,k; node f,g; queue<node>q; f.x=x;f.y=y;f.num=0; q.push(f); while(!q.empty()) { f=q.front(); q.pop(); for(i=0;i<4;i++) { g.x=f.x+dir[i][0]; g.y=f.y+dir[i][1]; if(g.x<0||g.y<0||g.x>=n||g.y>=m||e[g.x][g.y]=='*'||vis[g.x][g.y])continue; vis[g.x][g.y]=1; g.num=f.num+1; if(e[g.x][g.y]!='.') { if(e[g.x][g.y]=='@')path[from][0]=g.num; else if(e[g.x][g.y]=='<')path[from][l+1]=g.num; else path[from][e[g.x][g.y]-'A'+1]=g.num; } q.push(g); } }}void dfs(int pre,int time,int value){ if(time>t||ans==sum)return ; if(pre==l+1) { ans=max(ans,value); return ; } for(int i=1;i<=l+1;i++) { if(mark[i])continue; mark[i]=1; dfs(i,time+path[pre][i],value+val[i-1]); mark[i]=0; }}int main(){ int T,tt=0; scanf("%d",&T); while(T--) { int i,j,k; sum=0; scanf("%d%d%d%d",&m,&n,&t,&l); for(i=0;i<l;i++){scanf("%d",&val[i]);sum+=val[i];} val[l]=0; for(i=0;i<n;i++)scanf("%s",e[i]); for(i=0;i<=l+1;i++) { for(j=0;j<=l+1;j++) path[i][j]=INF; } for(i=0;i<n;i++) { for(j=0;j<m;j++) { if(e[i][j]=='@')bfs(i,j,0); if(e[i][j]=='<')bfs(i,j,l+1); if(e[i][j]<='J'&&e[i][j]>='A')bfs(i,j,e[i][j]-'A'+1); } } ans=-1; memset(mark,0,sizeof(mark)); dfs(0,0,0); printf("Case %d:n",++tt); if(ans==-1)printf("Impossiblen"); else printf("The best score is %d.n",ans); if(T!=0)printf("n"); } return 0;}
