#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5,INF=1e9;
int T,n,m,c[N],lgh[N],yyc[N],psj[N],*a[N],*sum[N],*num[N],dp[N][3];
struct Node{int l,r,val;};
inline int read(){
	int ret=0;char ch=getchar();
	while(ch<'0'||ch>'9')	ch=getchar();
	while(ch>='0'&&ch<='9')	ret=(ret<<1)+(ret<<3)+(ch^48),ch=getchar();
	return ret;
}
inline void write(int x){
	if(!x){puts("0");return;}
	else if(x==-1){puts("-1");return;}
	int num[15]={0};
	while(x)	num[++num[0]]=x%10,x/=10;
	for(int i=num[0];i;i--)	putchar(48^num[i]);
	putchar('\n');
}
void solve(){
	n=read(),m=read();
	for(int i=1;i<=n;i++)	c[i]=read();
	for(int i=1;i<=m;i++)	a[i]=lgh+(i-1)*n,sum[i]=yyc+(i-1)*n,num[i]=psj+(i-1)*n;
	for(int i=1;i<=m;i++)	for(int j=1;j<=n;j++)	a[i][j]=read();
	for(int i=1;i<=n;i++)	if(c[i]&&a[1][i]){write(-1);return;}
	for(int i=2;i<=m;i++){
		bool tag=0;
		for(int j=1;j<=n;j++)	if(!a[i][j]){tag=1;break;}
		if(!tag){write(-1);return;}
	}
	for(int i=1;i<=n;i++)	sum[1][i]=a[1][i];
	for(int i=2;i<=m;i++)	for(int j=1;j<=n;j++)	sum[i][j]=sum[i-1][j]+a[i][j];
	for(int i=1;i<=m;i++){
		num[i][1]=(a[i][1]>0);
		for(int j=2;j<=n;j++)	num[i][j]=num[i][j-1]+(a[i][j]>0);
	}
	vector<Node> f(0);
	for(int i=1;i<=n;i++)	if(!a[m][i])	f.push_back((Node){i,i,sum[m][i]});
	for(int dep=m-1;dep>=1;dep--){
		vector<Node> ok(0),no(0),base;
		for(Node i:f){
			int val=(i.l==1?num[dep][i.r]:num[dep][i.r]-num[dep][i.l-1]);
			if(val==i.r-i.l+1)	no.push_back(i);
			else	ok.push_back(i);
		}
		base=no;
		for(int i=n,lst=n+1,nowsum=0;i>=1;i--){
			if(!a[dep][i])	lst=i,nowsum=sum[dep][i];
			while(no.size()&&no.back().r==i){
				Node now=no.back();no.pop_back();
				if(lst!=n+1)	now.r=lst,now.val+=nowsum,ok.push_back(now);
			}
			if(a[dep][i])	nowsum+=sum[dep][i];
		}
		reverse(base.begin(),base.end());
		for(int i=1,lst=0,nowsum=0;i<=n;i++){
			if(!a[dep][i])	lst=i,nowsum=sum[dep][i];
			while(base.size()&&base.back().l==i){
				Node now=base.back();base.pop_back();
				if(lst!=0)	now.l=lst,now.val+=nowsum,ok.push_back(now);
			}
			if(a[dep][i])	nowsum+=sum[dep][i];
		}
		sort(ok.begin(),ok.end(),[&](const Node &x,const Node &y){
			return (x.l==y.l?x.r>y.r:x.l>y.l);
		});
		f.clear();
		while(ok.size()){
			if(f.size()&&f.back().l==ok.back().l&&f.back().r==ok.back().r)
				f.back().val=min(f.back().val,ok.back().val);
			else	f.push_back(ok.back());
			ok.pop_back();
		}
	}
		// for(Node i:f)	cout<<i.l<<" "<<i.r<<" "<<i.val<<endl;
	for(int i=1;i<=n;i++)	dp[i][0]=dp[i][1]=dp[i][2]=INF;
	dp[0][0]=dp[0][2]=0,dp[0][1]=INF;
	reverse(f.begin(),f.end());
	int ans=INF;
	for(int i=0;i<n;i++){
		if(c[i])	dp[i][0]=INF;
		dp[i+1][0]=min(dp[i+1][0],dp[i][0]);
		dp[i+1][2]=min(dp[i+1][2],dp[i][0]+a[1][i+1]);
		dp[i+1][1]=min(dp[i+1][1],dp[i][1]+a[1][i+1]);
		dp[i+1][0]=min(dp[i+1][0],dp[i][1]);
		dp[i+1][2]=min(dp[i+1][2],dp[i][2]+a[1][i+1]);
		while(f.size()&&f.back().l==i+1){
			Node now=f.back();f.pop_back();
			int mn=min(min(dp[i][0],dp[i][1]),dp[i][2]);
			if(now.r==n)	ans=min(ans,mn+now.val);
			else{
				dp[now.r+1][0]=min(dp[now.r+1][0],mn+now.val);
				dp[now.r+1][1]=min(dp[now.r+1][1],mn+now.val+a[1][now.r+1]);
				dp[now.r+1][2]=min(dp[now.r+1][2],mn+now.val+a[1][now.r+1]);
			}
		}
	}
	if(c[n])	dp[n][0]=INF;
	ans=min(ans,dp[n][0]),ans=min(ans,dp[n][1]);
	cout<<ans<<endl;
}
int main(){
	T=read();
	while(T--)	solve();
	return 0;
}