#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;

#define N 201
#define M 14

int n,m,tot;
int a[N][N];
int tx[M],ty[M];

int dis[M][M];
struct node
{
    int x,y,d;
}now,nxt;
queue<node>q;
int f[N][N];
bool vis[N][N];

int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};

int dp[1<<M][M];

void bfs(int s)
{
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
            f[i][j]=1e9;
    now.d=0;
    if(!s)
    {
        now.x=1;
        for(int i=1;i<=m;++i)
            if(!vis[1][i] && a[1][i]!=-1)
            {
                now.y=i;
                q.push(now);
                vis[1][i]=true;
                f[1][i]=a[1][i];
            }
        now.x=n;
        for(int i=1;i<=m;++i)
            if(!vis[n][i] && a[n][i]!=-1)
            {
                now.y=i;
                q.push(now);
                vis[n][i]=true;
                f[n][i]=a[n][i];
            } 
        now.y=1;
        for(int i=1;i<=n;++i)
            if(!vis[i][1] && a[i][1]!=-1)
            {
                now.x=i;
                q.push(now);
                vis[i][1]=true;
                f[i][1]=a[i][1];
            }
        now.y=m;
        for(int i=1;i<=n;++i)
            if(!vis[i][m] && a[i][m]!=-1)
            {
                now.x=i;
                q.push(now);
                vis[i][m]=true;
                f[i][m]=a[i][m];
            }
    }
    else
    {
        now.x=tx[s];
        now.y=ty[s];
        q.push(now);
        vis[now.x][now.y]=true;
        f[now.x][now.y]=0;
    }
    while(!q.empty())
    {
        now=q.front();
        q.pop();
        vis[now.x][now.y]=false;
        for(int i=0;i<4;++i)
        {
            nxt.x=now.x+dx[i];
            nxt.y=now.y+dy[i];
            if(nxt.x && nxt.x<=n && nxt.y && nxt.y<=m && a[nxt.x][nxt.y]!=-1 && f[nxt.x][nxt.y]>f[now.x][now.y]+a[nxt.x][nxt.y])
            {
                f[nxt.x][nxt.y]=f[now.x][now.y]+a[nxt.x][nxt.y];
                if(!vis[nxt.x][nxt.y]) 
                {
                    q.push(nxt);
                    vis[nxt.x][nxt.y]=true;
                }
            }
        }
    }
    for(int i=1;i<=tot;++i) dis[s][i]=f[tx[i]][ty[i]];
}

int main()
{
    int T,S;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;++i)
            for(int j=1;j<=m;++j)
                scanf("%d",&a[i][j]);
        scanf("%d",&tot);
        for(int i=1;i<=tot;++i) 
        {
            scanf("%d%d",&tx[i],&ty[i]);
            tx[i]++;
            ty[i]++;
        }
        bfs(0);
        for(int i=1;i<=tot;++i) bfs(i);
        S=(1<<tot+1)-1;
        for(int i=1;i<=S;++i)
            for(int j=0;j<=tot;++j)
                dp[i][j]=1e9;
        for(int i=1;i<=tot;++i) dp[0][i]=dis[0][i]-a[tx[i]][ty[i]];
        for(int i=1;i<S;++i)
            for(int j=0;j<=tot;++j)
                if(!(i&1<<j))
                    for(int k=1;k<=tot;++k)
                        if(i&1<<k)
                            dp[i][j]=min(dp[i][j],dis[j][k]+dp[i^1<<k][k]);
        printf("%d\n",dp[S-1][0]);
    }
}