#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]; for (int x = 0; x <= j; ++x)
c[i][j] = min(c[i][j], c[i][x] + c[i][j - x]);
}
}
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]);
}
for (int x = 1; x <= n; ++x) {
for (int l = 0; l < 2; ++l) {
dp[i][i][x][l] = min(dp[i][i][x][l], f[i][i][l]);
}
}
dp[i][i][0][a[i] != b[i]] = 0;
f[i][i][a[i] != b[i]] = 0;
}
for (int len = 1; 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]);
if (jj <= k) dp[l][r][x][jj] = min(dp[l][r][x][jj], f[l + 1][r][j]);
jj = j + (x!=b[r]);
if (jj <= k) dp[l][r][x][jj] = min(dp[l][r][x][jj], f[l][r - 1][j]);
jj = j + (x!=b[l]) + (l != r && x != b[r]);
if (jj <= k) dp[l][r][x][jj] = min(dp[l][r][x][jj], min(dp[l + 1][r - 1][x][j], f[l + 1][r - 1][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();
}