#include <bits/stdc++.h>
using namespace std;
const int N = 105;
#define pb push_back
#define ll long long
ll a[N],b[N],cost[N][N],dp[N][N][13],tp[N][N][13];
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
   // freopen("in", "r", stdin);
	int T;
	cin >> T;
	while(T--){
		int n,k;
		cin >> n >> k;
		for(int i = 1;i <= n;i++)cin >> a[i];
		for(int i = 1;i <= n;i++)cin >> b[i];

		for(int i = 1;i <= n;i++){
			for(int j = 1;j <= n;j++){
				cin >> cost[i][j];
			}
		}
		for(int i = 0;i <= n + 1;i++){
			for(int j = 0;j <= n + 1;j++){
				for(int t = 0;t <= k;t++){
					dp[i][j][t] = (ll)1e12;
					tp[i][j][t] = (ll)1e12;
				}
			}
		}
		for(int l = 1;l <= n;l++){
            if(a[l] == b[l]){
                dp[l][l][0] = 0;
            }else{
                dp[l][l][1] = 0;
                dp[l][l][0] = cost[b[l]][1];
            }
		}
            for(int l = n;l >= 1;l--){
                    tp[l][l - 1][0] = 0;

            for(int cur = 0;cur <= k;cur++){
                    for(int r = l + 1;r <= n;r++){
                        if(b[l] == b[r]){
                            tp[l][r][cur] = min(tp[l][r][cur], tp[l][r - 1][cur]);
                        }else{
                            if(cur)tp[l][r][cur] = min(tp[l][r][cur], tp[l][r - 1][cur - 1]);
                        }

                        for(int i = l;i < r;++i){
                            for(int x = 0;x <= cur;x++){
                                    tp[l][r][cur] = min(tp[l][r][cur], tp[l][i][x] + tp[i + 1][r][cur - x]);
                                }
                            }
                        }
                }

			for(int r = l + 1;r <= n;r++){
                for(int x = 0;x <= k;x++){
                    dp[l][r][x] = min(dp[l][r][x], tp[l][r][x] + cost[b[l]][r - l + 1]);
                }


				for(int i = l;i < r;++i){
					for(int x = 0;x <= k;x++){
						for(int y = 0;x + y <= k;y++){
							dp[l][r][x + y] = min(dp[l][r][x + y], dp[l][i][x] + dp[i + 1][r][y]);
						}
					}
				}
			}
		}
		cout << dp[1][n][0] << ' ';
		for(int x = 1;x <= k;x++){
			dp[1][n][x] = min(dp[1][n][x], dp[1][n][x - 1]);
			cout << dp[1][n][x] << ' ';
		}
		cout << '\n';
	}
	return 0;
}