//递推
#include<iostream>
#include<algorithm>
using namespace std;
#define INF 1<<30
//用来返回在第x次第y城能选的最小金额
int main()
{
	//s城市数 c表演场次数 pro利润 trans交通费
	//pro[x][y]第x次在第y城表演的利润 trans[x][y]从x城到y城的费用 d[x][y]在第x次在y城表演，自下到上树的累计
	int s,c,pro[101][51],trans[101][101],i,j,k,m,x,d[51][101],currentmax,n,ans[11];
	cin>>n;
	for(m=1;m<=n;m++)
	{
		cin>>s>>c;
		for(i=1;i<=s;i++)
		{
			for(j=1;j<=c;j++)
			{
				cin>>pro[j][i];
			}
		}
		for(i=1;i<=s;i++)
		{
			for(j=1;j<=s;j++)
			{
				cin>>trans[i][j];
			}
		}
		for(j=1;j<=s;j++)
		{
			d[c][j]=pro[c][j];
		}
		for(i=c-1;i>=1;i--)
		{
			x=i+1;
			for(j=1;j<=s;j++)
			{
				currentmax=-INF;
				for(k=1;k<=s;k++)
				{
					if(-trans[j][k]+d[x][k]>currentmax)
					{
						currentmax=-trans[j][k]+d[x][k];
					}
				}
				d[i][j]=pro[i][j]+currentmax;
			}
		}	
		currentmax=-INF;
		for(i=1;i<=s;i++)
		{
			if(d[1][i]>currentmax)
			{
				currentmax=d[1][i];
			}
		}
		ans[m]=currentmax;
	}
	for(i=1;i<=n;i++)
	{
		cout<<ans[i]<<endl;
	}
	return 0;
}