/*
    題意：給出一個(gè)地圖，有K種需要采集的礦，挖掘礦，帶著礦都需要電量，分別為ai,bi，
           問收集完所有種類的最少時(shí)間，一個(gè)位置的礦可采可不采，未收集完不能返回原點(diǎn)
   
   像這種情況復(fù)雜一點(diǎn)的bfs,可以加priority_queue
   可以想象，只要保證每次到達(dá)一個(gè)狀態(tài)是最優(yōu)的，那么這些狀態(tài)的和也是最優(yōu)的，包括最后到達(dá)目標(biāo)狀態(tài)
   每次出隊(duì)的狀態(tài)是最優(yōu)的，在這里標(biāo)記訪問過！
   狀態(tài)：x,y,state(state表示收集了多少種，可用位壓縮)
*/
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;

struct Pos
{
    int x,y,time,state;
    Pos(int xx,int yy,int t,int kk)
    {
        x=xx;y=yy;time=t;state=kk;
    }
    bool operator<(const Pos &a)const{
        return time>a.time;
    }
};

int dir[4][2]={
    {0,1},{1,0},{0,-1},{-1,0}
};
char net[30][30];
bool vi[30][30][(1<<11)+5];
int sx,sy,R,C,K,P;
int a[11],b[11],cost[(1<<11)+5];

inline bool chk(int x,int y)
{    
    return x>=0&&x<R&&y>=0&&y<C;
}
int bfs()
{
    memset(vi,0,sizeof(vi));
    priority_queue<Pos>Q;
    Q.push(Pos(sx,sy,0,0));
    while(!Q.empty()){
        Pos top=Q.top();Q.pop();
        int x=top.x,y=top.y,state=top.state,time=top.time+cost[state]+1;//是到達(dá)nx,ny的時(shí)間
        if(vi[x][y][state]||time>P)continue;
        vi[x][y][state]=1;//第一次出來的是最優(yōu)的，在這里標(biāo)記訪問過
        for(int k=0;k<4;k++){
            int nx=x+dir[k][0],ny=y+dir[k][1];
            if(!chk(nx,ny)||net[nx][ny]=='#'||vi[nx][ny][state])continue;
            if(nx==sx&&ny==sy){
                if(state==(1<<K)-1)return time;
                continue;
            }
            if(net[nx][ny]<='Z'&&net[nx][ny]>='A'){//可采可不采
                int t=net[nx][ny]-'A';
                if((state&(1<<t))==0){
                    if(!vi[nx][ny][state|(1<<t)]&&time+a[t]<=P)
                        Q.push(Pos(nx,ny,time+a[t],state|(1<<t)));
                }
            }
            Q.push(Pos(nx,ny,time,state));
        }
    }
    return -1;
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d%d%d",&R,&C,&K,&P);
        for(int i=0;i<R;i++){
            getchar();
            for(int j=0;j<C;j++){
                net[i][j]=getchar();
                if(net[i][j]=='*')sx=i,sy=j;
            }
        }
        for(int i=0;i<K;i++)
            scanf("%d%d",&a[i],&b[i]);

        memset(cost,0,sizeof(cost));
        for(int t=0;t<(1<<K);t++)
            for(int j=0;j<K;j++)
                if(t&(1<<j))cost[t]+=b[j];
        int ans=bfs();
        if(ans==-1)puts("Impossible");
        else printf("%d\n",ans);
    }
    return 0;
}