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

const int MAXN = 1000, MAXM = 100000, inf = 1e9;

namespace ISAP {
    struct Edge {
        int v, flow, nxt;
        Edge() {}
        Edge(int v, int f, int n) : v(v), flow(f), nxt(n) {}
    } E[MAXM];
    int G[MAXN], cur[MAXN], pre[MAXN], dis[MAXN], gap[MAXN];
    int N, S, T, sz;
    void init(int _n, int _s, int _t) {
        N = _n, S = _s, T = _t; sz = 0;
        for (int i = 0; i < N; ++ i) G[i] = -1;
    }
    inline void addedge(int u, int v, int f) {
        E[sz] = Edge(v, f, G[u]); G[u] = sz ++;
        E[sz] = Edge(u, 0, G[v]); G[v] = sz ++;
    }
    int flow() {
        int maxflow = 0, aug = inf;
        int u, v;
        for (int i = 0; i < N; ++ i) cur[i] = G[i], gap[i] = dis[i] = 0;
        gap[S] = N; u = pre[S] = S;
        while (dis[S] < N) {
            bool flag = false;
            for (int &now = cur[u]; ~now; now = E[now].nxt) {
                if (E[now].flow > 0 && dis[u] == dis[v = E[now].v] + 1) {
                    if (E[now].flow < aug) aug = E[now].flow;
                    pre[v] = u; u = v; flag = true;
                    if (u == T) {
                        maxflow += aug;
                        while (u != S) {
                            u = pre[u];
                            E[cur[u]].flow -= aug;
                            E[cur[u] ^ 1].flow += aug;
                        }
                        aug = inf;
                    }
                    break;
                }
            }
            if (flag) continue;
            int mindis = N;
            for (int now = G[u]; ~now; now = E[now].nxt) {
                if (E[now].flow > 0 && dis[E[now].v] < mindis) {
                    mindis = dis[E[now].v]; cur[u] = now;
                }
            }
            if ((-- gap[dis[u]]) == 0) break;
            ++ gap[dis[u] = mindis + 1]; u = pre[u];
        }
        return maxflow;
    }
}

int A[MAXN], B[MAXN], S[MAXN];
int N, M;

int main() {
    int T; scanf("%d", &T);
    for (int cas = 1; cas <= T; ++ cas) {
        scanf("%d%d", &N, &M);
        ISAP::init(N * 2 + 10, N * 2 + 2, N * 2 + 3);
        int fullflow = 0;
        for (int i = 0; i < N; ++ i) {
            scanf("%d%d%d", A + i, B + i, S + i);
            int need = S[i] / M + (S[i] % M != 0);
            fullflow += need;
            ISAP::addedge(ISAP::S, i, need);
            ISAP::addedge(i + N, ISAP::T, need);
        }
        for (int i = 0; i < N; ++ i) {
            for (int j = 0; j < N; ++ j) {
                int clean; scanf("%d", &clean);
                if (i == j) continue;
                if (B[i] + clean < A[j]) ISAP::addedge(i, j + N, inf);
            }
        }
        for (int i = 0; i < N; ++ i) {
            ISAP::addedge(i, N * 2, inf);
            ISAP::addedge(N * 2 + 1, i + N, inf);
        }
        int ret = 0, nowflow = 0;
        for (ret = 1; ; ++ ret) {
            ISAP::addedge(N * 2, N * 2 + 1, 1);
            nowflow += ISAP::flow();
            if (nowflow == fullflow) break;
        }
        printf("Case %d: %d\n", cas, ret);
    }
    return 0;
}