#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif
//#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
int n, k;
const int maxN = 105;
int a[maxN], b[maxN];
const int maxK = 11;
int dp_m[maxN][maxN][maxK];
int dp_g[maxN][maxN][maxK];
int dp_s[maxN][maxN][maxK];
const int INF = 1e9;
int A[maxN][maxN];
int help[maxN][maxN][maxK];
int suf_help[maxN][maxN][3][maxK];
mt19937 rnd(228);
void solve() {
    cin >> n >> k;
//    n = rnd() % 4 + 1;
//    k = rnd() % 3 + 1;
//    cout << n << " " << k << endl;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
//        a[i] = rnd() % n + 1;
//        cout << a[i] << " ";
    }
//    cout << endl;
    for (int i = 1; i <= n; i++) {
        cin >> b[i];
//        b[i] = rnd() % n + 1;
//        cout << b[i] << " ";
    }
//    cout << endl;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> A[i][j];
//            A[i][j] = A[i][j - 1] + (rnd() % 10);
//            cout << A[i][j] << " ";
        }
//        cout << endl;
    }
//    cout << endl;
//    priority_queue<pair<int, vector<int>>> pq;
//    vector<int> x(n);
//    for (int i = 0; i < n; i++) x[i] = a[i + 1];
//    pq.push({0, x});
//    map<vector<int>,int> dst;
//    dst[x] = 0;
//    b[0] = b[n + 1] = 0;
//    while (!pq.empty()) {
//        auto it = pq.top();
//        pq.pop();
//        it.first *= -1;
//        if (dst[it.second] != it.first) continue;
//        for (int l = 0; l < n; l++) {
//            for (int r = l; r < n; r++) {
//                for (int who = 1; who <= n; who++) {
//                    vector<int> y = it.second;
//                    for (int z = l; z <= r; z++) y[z] = who;
//                    int cost = it.first + A[who][r - l + 1];
//                    if (!dst.count(y) || dst[y] > cost) {
//                        dst[y] = cost;
//                        pq.push({-dst[y], y});
//                    }
//                }
//            }
//        }
//    }
    for (int i = 0; i <= n + 1; i++) {
        for (int j = 0; j <= n + 1; j++) {
            for (int t = 0; t <= k; t++) {
                dp_m[i][j][t] = INF;
                dp_g[i][j][t] = INF;
                dp_s[i][j][t] = INF;
                if (i > j) {
                    dp_m[i][j][t] = dp_s[i][j][t] = 0;
                    if (b[i] == b[j]) {
                        dp_g[i][j][t] = 0;
                    }
                }
            }
        }
    }
    for (int l = n; l >= 1; l--) {
        for (int r = l; r <= n; r++) {
            if (l == r) {
                for (int c = 0; c <= k; c++) {
                    if (c > 0) {
                        dp_m[l][r][c] = dp_s[l][r][c] = 0;
                        if (b[l - 1] == b[r + 1]) dp_g[l][r][c] = 0;
                    }
                    else {
                        dp_m[l][r][c] = A[b[l]][1];
                        dp_s[l][r][c] = ((a[l] == b[l]) ? 0 : A[b[l]][1]);
                        if (b[l - 1] == b[r + 1]) {
                            dp_g[l][r][c] = ((b[l - 1] == b[l]) ? 0 : A[b[l]][1]);
                        }
                    }
                }
                continue;
            }

            for (int mid = l; mid < r; mid++) {
                for (int was = 0; was <= k; was++) {
                    for (int will = 0; will + was <= k; will++) {
                        dp_m[l][r][was + will] = min(dp_m[l][r][was + will], dp_m[l][mid][was] + dp_m[mid + 1][r][will]);
                        dp_s[l][r][was + will] = min(dp_s[l][r][was + will], dp_s[l][mid][was] + dp_s[mid + 1][r][will]);
                    }
                }
            }

            if (b[l - 1] == b[r + 1]) {
                for (int mid = l; mid <= r; mid++) {
                    if (b[mid] == b[l - 1]) {
                        for (int was = 0; was <= k; was++) {
                            for (int will = 0; will + was <= k; will++) {
                                dp_g[l][r][was + will] = min(dp_g[l][r][was + will],
                                                             dp_m[l][mid - 1][was] + dp_g[mid + 1][r][will]);
                            }
                        }
                    }
                }
            }

            for (int was = 0; was <= k; was++) {
                if (b[l] == b[r]) {
                    dp_m[l][r][was] = min(dp_m[l][r][was], dp_g[l + 1][r - 1][was] + A[b[l]][r - l + 1]);
                    dp_s[l][r][was] = min(dp_s[l][r][was], dp_g[l + 1][r - 1][was] + A[b[l]][r - l + 1]);
                }
            }
        }
    }
    for (int i = 0; i <= k; i++) {
//        cout << dp[1][n][i] << " ";
//        int mn = INF;
//        for (auto& it : dst) {
//            auto y = it.first;
//            int val = it.second;
//            int T = 0;
//            for (int d = 0; d < n; d++) {
//                if (y[d] != b[d + 1]) T++;
//            }
//            if (T <= i) {
//                mn = min(mn, val);
//            }
//        }
//        cout << dp_s[1][n][i] << " " << mn << " ??? " << " " << i << endl;
//        assert(mn == dp_s[1][n][i]);
        cout << dp_s[1][n][i] << " ";
    }
    cout << '\n';
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
#ifdef DEBUG
    freopen("input.txt", "r", stdin);
#endif
    int tst = 1000;
    cin >> tst;
    while (tst--) solve();
    return 0;
}