/*
    题意：给出一个地图，有K种需要采集的矿，挖掘矿，带着矿都需要电量，分别为ai,bi，
           问收集完所有种类的最少时间，一个位置的矿可采可不采，未收集完不能返回原点
   
   像这种情况复杂一点的bfs,可以加priority_queue
   可以想象，只要保证每次到达一个状态是最优的，那么这些状态的和也是最优的，包括最后到达目标状态
   每次出队的状态是最优的，在这里标记访问过！
   状态：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;//是到达nx,ny的时间
        if(vi[x][y][state]||time>P)continue;
        vi[x][y][state]=1;//第一次出来的是最优的，在这里标记访问过
        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;
}