#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
#define ll long long
#define ull unsigned long long
#define int long long
#define SZ(x) ((int)((x).size()))
#define ALL(x) (x).begin(),(x).end()
using namespace std;
inline int read()
{
	char c=getchar();int x=0;bool f=0;
	for(;!isdigit(c);c=getchar())f^=!(c^45);
	for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
	return f?-x:x;
}

#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,ll>pii;
typedef vector<int>vi;

#define maxn 1000005
#define inf 0x3f3f3f3f3f3f3f3f

int n,m,c[maxn];

struct node{
    int l,r,w;
};
vi a[maxn],sum[maxn];

int ss[maxn];
int pre[maxn],suf[maxn];

pii tol[maxn];

vector<pii>buc[maxn];
int dp[maxn][2];
void cmin(int &x,int y){
    x=min(x,y);
}
int f[105][105][105];

int sc[maxn];
void work(int O)
{
    cin>>n>>m;
    if(n>100 ||m >100)exit(0);
    For(i,0,m){
        a[i].resize(n+1);
        sum[i].resize(n+1);
    }

    For(i,0,n) buc[i].clear();
    For(i,0,n+1) pre[i]=suf[i]=0;

    For(i,1,n)cin>>c[i];
    For(i,1,m){
        For(j,1,n){
            cin>>a[i][j];
            sum[i][j]=sum[i-1][j]+a[i][j];
        }
    }
    
    if(O==3){
    	cout<<n<<"  "<<m<<"\n";
    	For(i,1,n)cout<<c[i]<<" " ; cout<<"\n";
    	For(i,1,m){
    		For(j,1,n)cout<<a[i][j]<<" ";
    		cout<<"\n";
		}
		exit(0);
	}

    memset(f,63,sizeof f);

    For(i,1,n)
        if(a[m][i]==0){
            f[m][i][i]=sum[m][i];
        }
    
    Rep(t,m-1,1){
        Rep(i,n,1) For(j,i,n) {
            f[t][i][j]=min(f[t+1][i][j],min(f[t][i+1][j]+sum[t][i],f[t][i][j-1]+sum[t][j]));
        }
        For(i,1,n) ss[i]=ss[i-1]+sum[t][i],sc[i]=sc[i-1]+(a[t][i]==0);
        For(i,1,n) For(j,i,n) if(sc[j]-sc[i-1]==0) f[t][i][j]=inf;
    }

    For(l,1,n)
        For(r,l,n){
            int w=f[1][l][r];
            if(w<inf)buc[l].pb(mkp(r,w));//cout<<"l,r "<<l<<" "<<r<<" "<<w<<"\n";
        }
    
    For(i,0,n+1) For(j,0,2) dp[i][j]=inf;
    dp[0][0]=0;
    For(i,1,n){
        if(c[i] && a[1][i]){
            puts("-1");
            return;
        }
    }
    For(i,1,n){
        cmin(dp[i][2],min(dp[i-1][0],dp[i-1][2])+a[1][i]);
        cmin(dp[i][1],dp[i-1][1]+a[1][i]);
        cmin(dp[i][0],min(dp[i-1][0],dp[i-1][1]));
        for(auto [r,w]:buc[i]) {
            cmin(dp[r][1],min(dp[i-1][0],dp[i-1][2])+w);
        }
        if(c[i]) dp[i][0]=inf; 
    }
    int res=inf;
    For(i,0,1) res=min(res,dp[n][i]);
    if(res==inf)puts("-1");
    else cout<<res<<"\n";
}

signed main()
{
 //   freopen("data.in","r",stdin);
 //   freopen("std.out","w",stdout);
    int T;cin>>T;
    For(_,1,T)work(_);
    return 0;
}
/*
1
3 4
1 0 1
0 1 0
2 0 0
0 0 3
4 5 0
*/