#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][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[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--){
				for(int r = 0;r <= n + 1;r++){
					for(int y = 0;y <= k;y++){
						tp[r][y] = (ll)1e12;
					}
				}

				for(int y = 0;y <= k;y++){
					tp[l][y] = 0;
				}
				for(int r = l + 1;r <= n;r++){
					for(int y = 0;y <= k;y++){
						tp[r][y] = (ll)1e12;
					}
					if(b[r] == b[l]){
                        for(int x = 0;x <= k;x++){
                            //tp[r][x] = tp[r - 1][x];
                        }
					}
                    for(int j = l;j < r;j++){
                        for(int y = 0;y <= k;y++){
                            for(int x = 0;x + y <= k;x++){
                                tp[r][x + y] = min(tp[r][x + y], tp[j][x] + dp[j + 1][r][y]);
                            }
                        }
                    }

				}

			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[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;
}