#include <cstdio>  #include <cstring>  #include <algorithm>  #include <vector>  #include <queue>using namespace std; #define Max(a,b) (a>b?a:b)#define Min(a,b) (a>b?a:b)#define maxn 100int m, n, time, k, sorce[20];bool vis[1<<11][51][51];char map[52][52];typedef struct{    int step;    int x, y;    int sorce;    int stau;}Point;int bfs(Point P);int main(){    int i, j, T, ans, count = 1;    Point P;    scanf("%d",&T);    while(T--)    {        scanf("%d%d%d%d",&n,&m,&time,&k);                for(i=0; i<k; i++)            scanf("%d",&sorce[i]);                for(i=0; i<m; i++)        {            scanf("%s",map[i]);                        for(j=0; j < n; j++)            {                if(map[i][j] == ‘@‘)                    P.x = i, P.y = j, P.step = P.sorce = P.stau = 0;            }        }                ans = bfs(P);                printf("Case %d:\n",count++);        if(ans == -1)            printf("Impossible\n");        else            printf("The best score is %d.\n",ans);        if(T)            printf("\n");    }    return 0;}int bfs(Point P){    int i, max = -1, key;    int dir[4][2] = {1,0,0,1,-1,0,0,-1};    Point Pn;    queue <Point> q;    q.push(P);    memset(vis,0,sizeof(vis));    vis[P.stau][P.x][P.y] = 1;    while( !q.empty() )    {        P = q.front();        q.pop();        for(i=0; i<4; i++)        {            Pn.x = P.x + dir[i][0];            Pn.y = P.y + dir[i][1];            Pn.step = P.step + 1;            Pn.sorce = P.sorce;            Pn.stau = P.stau;            if(Pn.step > time)                break;            if(Pn.x>=0 && Pn.x<m && Pn.y>=0 && Pn.y<n && map[Pn.x][Pn.y] != ‘*‘)            {                if(map[Pn.x][Pn.y] == ‘<‘)                {                    max = Max(max,Pn.sorce);                    if(Pn.stau == ((1<<k)-1) )                        return max;                }                else if(map[Pn.x][Pn.y] >= ‘A‘ && map[Pn.x][Pn.y] <= ‘J‘)                {                    key = map[Pn.x][Pn.y] - ‘A‘;                    if( ((Pn.stau)&(1<<key)) == 0 )                    {                        Pn.sorce += sorce[key];                        Pn.stau += 1<<key;                    }                }                if( !vis[Pn.stau][Pn.x][Pn.y])                {                    vis[Pn.stau][Pn.x][Pn.y] = 1;                    q.push(Pn);                }                            }        }    }    return max;}