#include <bits/stdc++.h>
using namespace std;

int n, a[121], b[121], k;
int dp[121][121][121][31];
int C[121][121], f[121][121][31];

void solve() {
	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 >> C[i][j];
		}
	}	
	const int inf = 1e9 + 100;
	for (int i = 1; i <= n; ++i) {
		for (int j = i; j <= n; ++j) {
			for (int x = 0; x <= n; ++x) {
				for (int l = 0; l <= k; ++l) {
					f[i][j][l] = inf;
					dp[i][j][x][l] = inf;
				}
			}			
		}
	}
	for (int i = 1; i <= n; ++i) {		
		for (int x = 1; x <= n; ++x) {
			dp[i][i][x][x != b[i]] = 0;
			f[i][i][x != b[i]] = min(f[i][i][x != b[i]], C[x][1]);
		}
		dp[i][i][0][a[i] != b[i]] = 0;
		f[i][i][a[i] != b[i]] = 0;
	}
	for (int len = 2; len <= n; ++len) {
		for (int l = 1, r = len; r <= n; ++l, ++r) {
			for (int x = 1; x <= n; ++x) {				
				for (int j = 0; j <= k; ++j) {
					int jj = jj = j + (x!=b[l]) + (x != b[r]);
					if (jj <= k) dp[l][r][x][jj] = min(dp[l][r][x][jj], dp[l + 1][r - 1][x][j]);
				}				
				for (int j = 0; j <= k; ++j) {
					f[l][r][j] = min(f[l][r][j], C[x][len] + dp[l][r][x][j]);
				}
			}
			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][0][x + y] = min(dp[l][r][0][x + y], f[l][i][x] + f[i + 1][r][y]);
						f[l][r][x + y] = min(f[l][r][x + y], dp[l][r][0][x + y]);
					}
				}
			}
		}
	}
	//~ n = 3;
	//~ cout << dp[2][4][2][0] << '\n';
	//~ cout << f[1][4][0] << '\n';
	int ans = f[1][n][0];
	cout << ans << " ";
	for (int i = 1; i <= k; ++i) {
		ans = min(ans, f[1][n][i]);
		cout << ans << " \n"[i == k];
	}
		
}


int main() {
	cin.tie(0)->sync_with_stdio(0);
	int t = 1;
	cin >> t;
	while (t--) solve();
}