#include <iostream>#include <cstdio>#include <algorithm>#include <queue>using namespace std;const int INF=0xfffffff;int n,m,L,M,ans,sum;int dis[20][20];char mp[55][55];struct node{    int x,y,step,v;}kk[20];int dx[]={1,-1,0,0};int dy[]={0,0,1,-1};int vis[55][55];int bfs(node s,node t){    memset(vis,0,sizeof(vis));    queue <node> q;    s.step=0;    q.push(s);    vis[s.x][s.y]=1;    while(!q.empty()){        node u=q.front();        if(u.x==t.x && u.y==t.y)            return u.step;        q.pop();        for(int i=0;i<4;i++){            int xx=u.x+dx[i];            int yy=u.y+dy[i];            if(xx<0 || xx>=n || yy<0 || yy>=m)continue;            if(mp[xx][yy]==‘*‘)continue;            if(!vis[xx][yy]){                vis[xx][yy]=1;                node next=u;                next.step++;next.x=xx;next.y=yy;                if(next.step<=L)q.push(next);            }        }    }    return INF;}int VIS[20];void dfs(int now,int t,int v){    if(ans==sum)return;    if(t>L)return;    if(now==M+1){        ans=max(ans,v);        return;    }    for(int i=1;i<=M+1;i++){        if(VIS[i])continue;        VIS[i]=1;        dfs(i,t+dis[now][i],v+kk[i].v);        VIS[i]=0;    } }int V[20];int main(){    int T;    scanf("%d",&T);    int first=1;    for(int cas=1;cas<=T;cas++){        scanf("%d%d%d%d",&m,&n,&L,&M);        sum=ans=0;        for(int i=1;i<=M;i++){            scanf("%d",&V[i]);            sum+=V[i];        }        for(int i=0;i<n;i++)            scanf("%s",mp[i]);        for(int i=0;i<n;i++){            for(int j=0;j<m;j++){                if(mp[i][j]==‘@‘){                    kk[0].x=i;kk[0].y=j;kk[0].v=0;                }                else if(mp[i][j]==‘<‘){                    kk[M+1].x=i;kk[M+1].y=j;kk[M+1].v=0;                }                else if(mp[i][j]>=‘A‘ && mp[i][j]<=‘J‘){                    kk[mp[i][j]-‘A‘+1].x=i;kk[mp[i][j]-‘A‘+1].y=j;kk[mp[i][j]-‘A‘+1].v=V[mp[i][j]-‘A‘+1];                }            }        }        memset(dis,-1,sizeof(dis));        for(int i=0;i<=M+1;i++){            for(int j=0;j<=M+1;j++){                if(i==j)dis[i][j]=0;                else{                    if(dis[i][j]==-1){                        dis[i][j]=bfs(kk[i],kk[j]);                        dis[j][i]=dis[i][j];                    }                }            }        }        memset(VIS,0,sizeof(VIS));        VIS[0]=1;        dfs(0,0,0);        if(first)first=0;        else putchar(‘\n‘);        printf("Case %d:\n",cas);        if(dis[0][M+1]==INF)puts("Impossible");        else printf("The best score is %d.\n",ans);    }    return 0;}