# include <bits/stdc++.h>
# define int long long
using namespace std;
const int N = 105; 
int n, K, A[N][N], dp[N][N][12], mn[N][N][12], a[N], b[N], f[N][12]; 
void chkmin(int &x, int y) { x = min(x, y); return; }
signed main(void)
{
    int Test; scanf("%lld", &Test); 
    while(Test--)
    {
        scanf("%lld%lld", &n, &K); 
        for(int i = 1; i <= n; i++) scanf("%lld", &a[i]); 
        for(int i = 1; i <= n; i++) scanf("%lld", &b[i]); 
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++) scanf("%lld", &A[i][j]); 
        for(int l = 0; l <= n + 1; l++)
        {
            for(int r = 0; r <= n + 1; r++)
            {
                for(int d = 0; d <= K; d++) 
                {
                    dp[l][r][d] = mn[l][r][d] = INT_MAX; 
                }
            }
        }
        for(int i = 1; i <= n; i++) 
        {
            dp[i][i][0] = A[b[i]][1]; mn[i][i][0] = 0; 
            for(int j = 1; j <= K; j++) dp[i][i][j] = 0, mn[i][i][j] = 0; 
        }
        
        for(int len = 2; len <= n; len++)
        {
            for(int l = 1, r = len; r <= n; l++, r++)
            {
                for(int i = (b[l] == b[r] ? 0 : 1); i <= min(len, K); i++) 
                    mn[l][r][i] = mn[l][r - 1][i - (b[l] != b[r])]; 
                for(int k = len; k <= K; k++) dp[l][r][k] = mn[l][r][k] = 0; 
                for(int p = l; p < r; p++) 
                {
                    for(int k = 0; k <= min(len, K); k++)
                    {
                        for(int x = 0; x <= k; x++)
                        {
                            chkmin(dp[l][r][k], dp[l][p][x] + dp[p + 1][r][k - x]); 
                            chkmin(mn[l][r][k], mn[l][p][x] + dp[p + 1][r][k - x]); 
                        }
                    }
                }
                // for(int k = 1; k <= K; k++) chkmin(mn[l][r][k], mn[l][r][k - 1]); 
                for(int k = 0; k <= K; k++) 
                {
                    chkmin(dp[l][r][k], mn[l][r][k] + A[b[l]][len]);
                    // if(k) chkmin(dp[l][r][k], dp[l][r][k - 1]); 
                }
            }
        }

        for(int i = 0; i <= n + 1; i++)
            for(int j = 0; j <= K; j++) 
                f[i][j] = i == 0 ? 0 : INT_MAX; 
        for(int i = 1; i <= n; i++)
        {
            for(int j = 0; j <= min(i, K); j++) 
            {
                // no 
                if(a[i] == b[i]) f[i][j] = f[i - 1][j]; 
                else if(j > 0) f[i][j] = f[i - 1][j - 1]; 
                for(int p = 0; p < i; p++) 
                {
                    for(int x = 0; x <= j; x++) 
                    {
                        chkmin(f[i][j], f[p][x] + dp[p + 1][i][j - x]); 
                    }
                }
                // if(j) chkmin(f[i][j], f[i][j - 1]); 
            }
        }
        for(int i = 0; i <= K; i++) printf("%lld%c", f[n][i], " \n"[i == K]); 
    }
    return 0; 
}