#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;
};
vector<node>f[maxn];
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 qr[maxn],qw[maxn],sc[maxn];
void wk(vector<node>&vec){
    For(i,1,n) qr[i]=inf;
    for(auto [l,r,w]:vec){
        if(r<qr[l]) qr[l]=r,qw[l]=w;
    }
    vector<node>qwq;
    For(i,1,n) if(qr[i]!=inf) qwq.pb({i,qr[i],qw[i]});
    vec=qwq;
}

void work()
{
    cin>>n>>m;
    For(i,0,m){
        a[i].resize(n+1);
        sum[i].resize(n+1);
    }

    For(i,0,m+1) f[i].clear();
    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];
        }
    }
    For(i,1,n)
        if(a[m][i]==0){
            f[m].pb({i,i,sum[m][i]});
        //    cout<<"lst "<<i<<" "<<sum[m][i]<<"\n";
        }
    Rep(t,m-1,1){
     //   cout<<"solve "<<t<<"\n";
        For(i,1,n){
            pre[i]=pre[i-1];
            if(a[t][i]==0)pre[i]=i;
        }
        Rep(i,n,1){
            suf[i]=suf[i+1];
            if(a[t][i]==0)suf[i]=i;
        }

        For(i,1,n) ss[i]=ss[i-1]+sum[t][i],sc[i]=sc[i-1]+(a[t][i]==0);

        vector<node>vec;
        auto add=[&](int l,int r,int w){
            vec.pb({l,r,w});
        };
        
        for(auto [l,r,w]:f[t+1]){
        	if(sc[r]-sc[l-1]>0){
        		add(l,r,w);
        		continue;
			}
            if(pre[l]) {
                int w2=ss[l-1]-ss[pre[l]-1];
                add(pre[l],r,w2+w);
            }
            if(suf[r]){
                int w2=ss[suf[r]]-ss[r];
                add(l,suf[r],w2+w);
            }
        }

        if(!vec.size()){
            puts("-1");
            return;
        }

        
        sort(vec.begin(),vec.end(),[&](node a,node b){
            return mkp(a.l,a.r)<mkp(b.l,b.r);
        });

        
       /* for(auto [l,r,w]:vec){
            cout<<"l,r,w "<<l<<" "<<r<<" "<<w<<"\n";
        }*/
        
        For(i,0,SZ(vec)-1){
            int mn=inf;
            int j=i;
            while(j+1<SZ(vec) && mkp(vec[i].l,vec[i].r)==mkp(vec[j+1].l,vec[j+1].r)) ++j;
            For(k,i,j) mn=min(mn,vec[k].w);
            i=j;
            f[t].pb({vec[i].l,vec[i].r,mn});
        }
        
        wk(f[t]);
    }

    for(auto [l,r,w]:f[1]){
        buc[l].pb(mkp(r,w));
    }
    
    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][2],dp[i-1][0])+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()
{
    int T;cin>>T;
    while(T--)work();
    return 0;
}
/*
1
3 4
1 0 1
0 1 0
2 0 0
0 0 3
4 5 0
*/