#include<cstdio>

 #include<iostream>

 #include<cstring>

 #include<string>

 #include<algorithm>

 #include<cstdlib>

 #include<cmath>

 using namespace std;

 const int MAXN =  + ;

 struct

 {

     int v[];

 }a[MAXN];

 int d[MAXN][MAXN];

 int dp[MAXN][MAXN];

 int main()

 {

     int n;

     scanf("%d", &n);

     while(n--)

     {

         memset(d, , sizeof d);

         memset(dp, , sizeof dp);

         int s, c;

         scanf("%d%d", &s, &c);

         for(int i = ; i <= s; ++i)

             for(int j = ; j <= c; ++j)

                 scanf("%d", &a[i].v[j]);

         for(int i = ; i <= s; ++i)

             for(int j = ; j <= s; ++j)

                 scanf("%d", &d[i][j]);

         for(int i = ; i <= s; ++i)

             dp[][i] = a[i].v[];

         for(int i = ; i <= c; ++i)

             for(int j = ; j <= s; ++j)

                for(int k = ; k <= s; ++k)

                     dp[i][j] = max(dp[i][j], dp[i - ][k] - d[k][j] + a[j].v[i]);

         int ans = ;

         for(int i = ; i <= s; ++i)

             ans = max(ans, dp[c][i]);

        printf("%d\n", ans);

     }

     return ;

 }