#include<bits/stdc++.h>
#define ull unsigned long long
#define ui unsigned int
#define ld long double
#define ll long long
#define lll __int128
#define fi first
#define se second
#define e emplace
#define eb emplace_back
#define db double
#define ef emplace_front
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vi vector<int>
#define vp vector<pii>
#define vt vector<tup>
#define all(x) x.begin(),x.end()
#define mp make_pair

#define FastI
#define FastO
#define int ll
bool ST;
static const ll MOD=1e9+7,Phi=998244352,inv2=499122177,Root=3,iRoot=332748118;
static const ll inf=1073741823,INF=4611686018427387903;
static const ld eps=1e-9,pi=3.1415926535;
char in[1<<20],*p1=in,*p2=in;
char out[1<<20],*p3=out;
using namespace std;
struct tup
{
	int x,y,z;
	tup(int X=0,int Y=0,int Z=0)
	{x=X,y=Y,z=Z;}
	bool operator <(const tup nd)const
	{return x<nd.x;}
};
#ifdef FastI
#define getchar() (p1==p2&&(p2=(p1=in)+fread(in,1,1<<20,stdin),p1==p2)?EOF:*p1++)
#endif
#ifdef FastO
#define putchar(x) (p3-out==1<<20?fwrite(out,1,1<<20,stdout),p3=out,0:0,*p3++=x)
#define puts(x) write(x,'\n')
#endif
namespace FastIO
{
	template<typename T> inline void write(T x,char ch=' ')
	{
		if(is_same<char,T>::value)putchar(x);
		else
		{
			if(x<0)x=-x,putchar('-');
			static char st[25];
			int top=0;
			do st[top++]=x%10+'0',x/=10;while(x);
			while(top)putchar(st[--top]);
		}
		ch!='~'?putchar(ch):0;
	}
	inline void write(const char*x,char ch=' ')
	{
		for(int i=0;x[i]!='\0';++i)putchar(x[i]);
		ch!='~'?putchar(ch):0;
	}
	inline void read(char&s){do s=getchar();while(s=='\n'||s==' ');}
	inline void read(char s[])
	{
		int len=0;char st;
		do st=getchar();while(st=='\n'||st==' ');
		s[++len]=st,st=getchar();
		while(st!='\n'&&st!=' '&&st!='\r')s[++len]=st,st=getchar();
		s[++len]='\0';
	}
	template<typename T> inline void read(T &s)
	{
		char ch=getchar();s=0;
		while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
		bool tf=(ch=='-'&&(ch=getchar()));
		while(ch>='0'&&ch<='9')s=(s<<1)+(s<<3)+ch-'0',ch=getchar();
		s=tf?-s:s;
	}
	inline void edl(){putchar('\n');}
	template<typename T1,typename T2> inline void read(pair<T1,T2> &s){read(s.fi),read(s.se);}
	template<typename T,typename...Args> inline void write(T x,Args...args){write(x,'~'),write(args...);}
	template<typename T,typename...Args> inline void read(T&x,Args&...args){read(x),read(args...);}
	#ifdef FastO
	struct Writer{~Writer(){fwrite(out,1,p3-out,stdout);}}Writ;
	#endif
}
using namespace FastIO;
namespace MTool
{
	inline int Cadd(int a,int b){return (ll)a+b>=MOD?(ll)a+b-MOD:a+b;}
	inline int Cdel(int a,int b){return a-b<0?a-b+MOD:a-b;}
	inline int Cmul(int a,int b){return 1ll*a*b%MOD;}
	inline int sqr(int a){return 1ll*a*a%MOD;}
	inline void Madd(int&a,int b){a=((ll)a+b>=MOD?(ll)a+b-MOD:a+b);}
	inline void Mdel(int&a,int b){a=(a-b<0?a-b+MOD:a-b);}
	inline void Mmul(int&a,int b){a=1ll*a*b%MOD;}
	inline int Cmod(int x){return (x%MOD+MOD)%MOD;}
	inline void Mmod(int&x){x=(x%MOD+MOD)%MOD;}
	template<typename T> inline bool Mmax(T&a,T b){return a<b?a=b,1:0;}
	template<typename T> inline bool Mmin(T&a,T b){return a>b?a=b,1:0;}
	template<typename...Args> inline void Madd(int&a,int b,Args...args){Madd(a,b),Madd(a,args...);}
	template<typename...Args> inline void Mmul(int&a,int b,Args...args){Mmul(a,b),Mmul(a,args...);}
	template<typename...Args> inline void Mdel(int&a,int b,Args...args){Mdel(a,b),Mdel(a,args...);}
	template<typename...Args> inline int Cadd(int a,int b,Args...args){return Cadd(Cadd(a,b),args...);}
	template<typename...Args> inline int Cmul(int a,int b,Args...args){return Cmul(Cmul(a,b),args...);}
	template<typename...Args> inline int Cdel(int a,int b,Args...args){return Cdel(Cdel(a,b),args...);}
	template<typename...Args,typename T> inline bool Mmax(T&a,T b,Args...args){return Mmax(a,b)|Mmax(a,args...);}
	template<typename...Args,typename T> inline bool Mmin(T&a,T b,Args...args){return Mmin(a,b)|Mmin(a,args...);}
	inline int power(int x,int y){int s=1;for(;y;y>>=1,Mmul(x,x))if(y&1)Mmul(s,x);return s;}
}
using namespace MTool;
namespace WrongAnswer_90
{
	int n,m,a[2000010],c[2000010];
	int pre[2000010],nex[2000010];
	int s[2000010],f[2000010],g[2000010];
	int id[2000010];
	vp trans[2000010];
	#define id(i,j) ((j)*(n+1)+(i))
	int F[20][2000010];
	inline int ask(int l,int r)
	{
		int k=__lg(r-l+1);
		return min(F[k][l],F[k][r-(1<<k)+1]);
	}
	inline int get(int i,int x,int y)
	{
		int l=0,r=i-1,mid;
		while(l<r)
		{
			mid=(l+r+1)>>1;
			if(ask(id(mid,y),id(i,y))<x)l=mid;
			else r=mid-1;
		}
		return l;
	}
	inline int getsum(int x1,int y1,int x2,int y2)
	{return s[id(x2,y2)]-s[id(x1-1,y2)]-s[id(x2,y1-1)]+s[id(x1-1,y1-1)];}
	int cnt;
	map<pii,int> hash[2000010];
	bool dbg;
	void mian()
	{
		read(m,n);
		if(dbg)cerr<<m<<" "<<n<<endl;
		for(int i=1;i<=n;++i)hash[i].clear();
		for(int i=0;i<=(n+1)*(m+1);++i)f[i]=INF,s[i]=pre[i]=nex[i]=0;
		for(int i=1;i<=m;++i)
		{
			read(c[i]);
			if(dbg)cerr<<c[i]<<" ";
		}
		if(dbg)cerr<<endl;
		for(int i=1;i<=n;++i,dbg?cerr<<endl,0:0)for(int j=1;j<=m;++j)
		{
			read(a[id(i,j)]);
			if(dbg)cerr<<a[id(i,j)]<<" ";
		}
		for(int i=1;i<=m;++i)if(c[i]&&a[id(1,i)])
		return puts("-1"),void();
		for(int i=1;i<=n;++i)for(int j=1;j<=m;++j)
		{
			if(!a[id(i,j)])pre[id(i,j)]=j;
			else if(j==1)pre[id(i,j)]=-1;
			else pre[id(i,j)]=pre[id(i,j-1)];
			F[0][id(i,j)]=pre[id(i,j)];
			s[id(i,j)]=a[id(i,j)]+s[id(i,j-1)]+s[id(i-1,j)]-s[id(i-1,j-1)];
		}
		for(int i=1;i<=n;++i)for(int j=m;j>=1;--j)
		{
			if(!a[id(i,j)])nex[id(i,j)]=j;
			else if(j==m)nex[id(i,j)]=m+1;
			else nex[id(i,j)]=nex[id(i,j+1)];
		}
		for(int i=1;i<20;++i)for(int j=1;j+(1<<i)-1<=(n+1)*(m+1);++j)
		F[i][j]=min(F[i-1][j],F[i-1][j+(1<<(i-1))]);
		cnt=0;
		for(int i=1;i<=m;++i)if(!a[id(n,i)])
		hash[n][mp(i,i)]=++cnt,f[cnt]=0;
		for(int i=n;i>1;--i)
		{
			for(auto [x,p]:hash[i])
			{
				int l=x.fi,r=x.se,nl,nr;
				int nx=get(i,l,r);
				auto upd=[&]()->void
				{
					if(hash[nx].find(mp(nl,nr))==hash[nx].end())
					hash[nx][mp(nl,nr)]=++cnt;
					Mmin(f[hash[nx][mp(nl,nr)]],f[p]+getsum(nx+1,l,i-1,r)+getsum(nx,nl,nx,nr));
				};
				if(!nx){nx=1,nl=l,nr=r,upd();continue;}
				nr=r,nl=pre[id(nx,r)];
				if(nl>=1)upd();
				nl=l,nr=nex[id(nx,l)];
				if(nr<=m)upd();
			}
		}
		pre[0]=0,nex[m+1]=m+1;
		vi ve={0};
		for(int i=1;i<=m;++i)
		{
			id[i]=id[i-1]+c[i];
			if(c[i])ve.eb(i);
		}
		for(int i=1;i<=m;++i)pre[i]=c[i]?i:pre[i-1];
		for(int i=m;i>=1;--i)nex[i]=c[i]?i:nex[i+1];
		for(int i=1;i<=id[m];++i)trans[i].clear();
		for(auto [x,p]:hash[1])
		{
			int l=x.fi-1,r=x.se;
			trans[id[r]].eb(mp(id[l]+1,f[p]));
			if(id[r]<id[m])
			trans[id[r]+1].eb(mp(id[l]+1,f[p]+getsum(1,r+1,1,ve[id[r]+1])));
			if(id[l])
			trans[id[r]].eb(mp(id[l],f[p]+getsum(1,ve[id[l]],1,l)));
			if(id[l]&&id[r]<id[m])
			trans[id[r]+1].eb(mp(id[l],f[p]+getsum(1,r+1,1,ve[id[r]+1])+getsum(1,ve[id[l]],1,l)));
		}
		f[0]=0;
		for(int i=1;i<=id[m];++i)
		{
			f[i]=INF;
			if(i>1)Mmin(f[i],f[i-1]+s[id(1,ve[i])]-s[id(1,ve[i-1])]);
			for(auto [x,y]:trans[i])if(x<=i)
			Mmin(f[i],f[x-1]+y,g[x-1]+y);
			if(i<id[m])
			g[i]=min(g[i-1],f[i-1])+s[id(1,ve[i+1]-1)]-s[id(1,ve[i]-1)];
		}
		write(f[id[m]]>=1e18?-1:f[id[m]],'\n');
	}
	inline void Mian()
	{
		int T=1,C;
		read(T);
		for(int _T=1;_T<=T;++_T)
		{
//			if(_T==41)dbg=1;
//			else dbg=0;
			mian();
		}
	}
}
bool ED;
signed main()
{
//	ios::sync_with_stdio(0);
//	freopen("1.in","r",stdin);
//	freopen("1.out","w",stdout);
	WrongAnswer_90::Mian();
	return 0;
}