#include <bits/stdc++.h>

using namespace std;

const int MAXN = 400;

int a[MAXN], b[MAXN], s[MAXN];
int clr[MAXN][MAXN];
int mat[MAXN][MAXN];
int f[MAXN][MAXN];

const int INF = 100000000;

int maxFlow(int n, const int mat[][MAXN], int s, int t, int f[][MAXN])
{
    int g[MAXN][MAXN] = {0}, cur[MAXN] = {0}, h[MAXN] = {0}, e[MAXN] = {0}, q[MAXN] = {0}, l[MAXN * 2][MAXN] = {0}, i, j, k, head, tail, ret, checked, p, o;
    for (i = 0; i < n; i++) {
        h[i] =  - 1;
        cur[i] = 1;
        for (e[i] = g[i][0] = j = 0; j < n; f[i][j++] = 0) {
            if (mat[i][j] || mat[j][i]) {
                g[i][++g[i][0]] = j;
            } 
        }
    }
    for (i = 0; i < 2 * n; i++) {
        l[i][0] = 0;
    }
    for (l[h[q[head = 0] = t] = 0][++l[0][0]] = t, tail = 1; head < tail; head++) {
        for (i = 1; i <= g[j = q[head]][0]; i++) {
            if (h[k = g[j][i]] < 0) {
                h[k] = h[j] + 1;
                q[tail++] = k;
                if (k != s) {
                    l[h[k]][++l[h[k]][0]] = k;
                } 
            }
        }
    }
    for (h[s] = n, i = 1; i <= g[s][0]; i++) {
        j = g[s][i];
        f[j][s] = -(f[s][j] = e[j] = mat[s][j]);
    }
    for (i = n; i; i--) {
        for (checked = 0, j = l[i][0]; j;) {
            if ((k = l[i][j]) == s) {
                j--;
            } else if (!e[k]) {     //Full
                if (checked) {      //Update
                    if (i && l[i][0] == 1) {
                        for (p = h[k] + 1; p < n; l[n][0] += l[p][0], l[p++][0] = 0) {
                            for (o = 1; o <= l[p][0]; o++) {
                                l[n][++l[n][0]] = l[p][o];
                                h[l[p][o]] = n;
                            }
                        }
                    }
                    l[h[k]][++l[h[k]][0]] = k;
                    l[i][j] = l[i][l[i][0]--];
                    i = h[k];
                    break;
                } else {
                    j--;
                } 
            } else if (cur[k] > g[k][0]) {  //Relabel
                for (checked = p = 1, o = INF; p <= g[k][0]; p++) {
                    if (mat[k][g[k][p]] > f[k][g[k][p]] && h[g[k][p]] < o) {
                        o = h[g[k][p]];
                    } 
                }
                h[k] = o + 1, cur[k] = 1;
            } else if ((o = mat[k][p = g[k][cur[k]]] - f[k][p]) && h[k] == h[p] + 1) {
                o = o < e[k] ? o : e[k];
                f[p][k] = -(f[k][p] += o);
                e[k] -= o;
                e[p] += o;
            } else {
                cur[k]++;
            } 
        }
    }
    for (ret = 0, i = 1; i <= g[s][0]; i++) {
        ret += f[s][g[s][i]];
    }
    return ret;
}

int main()
{
	int T;
	int ttt = 0;
	scanf("%d", &T);
	while (T--){
		ttt++;
		int n, m;
		scanf("%d%d", &n, &m);
		memset(mat, 0, sizeof(mat));
		for (int i = 1; i<=n; i++){
			scanf("%d%d%d", a+i, b+i, s+i);
			if (s[i]%m==0) s[i] /= m;
			else s[i] = s[i]/m+1;
		}
		for (int i = 1; i<=n; i++)
			for (int j = 1; j<=n; j++)
				scanf("%d", &clr[i][j]);
		int x, y;
		x = 2*n+2; y = 2*n+3;
		for (int i = 1; i<=n; i++){
			mat[0][i] = s[i];
			mat[i][x] = INF;
			for (int j = 1; j<=n; j++){
				if (b[i]+clr[i][j]<a[j]) mat[i][n+j] = INF;
			}
			mat[y][n+i] = INF;
			mat[n+i][2*n+1] = s[i];
		}
		int l = 1, r = 0;
		for (int i = 1; i<=n; i++)
			r += s[i];
		int tot = r;
		int ans = 0;
		while (l<=r){
			int mid = (l+r)/2;
			mat[x][y] = mid;
			//memset(f, 0, sizeof(f));
			int res = maxFlow(2*n+4, mat, 0, 2*n+1, f);
			if (res>=tot){
				r = mid-1;
				ans = mid;
			}
			else l = mid+1;
		}
		cout<<"Case "<<ttt<<": "<<l<<endl;
	}
}