#include<cstdio>
#include<cstring>
#include<queue>
#define MAXN 210
#define oo 12345678
#define MAXM 10010
using namespace std;
int n, m;
struct Edge {
	int v, f, w, nxt;
	Edge() {
	}
	Edge(int a, int b, int c, int d) {
		v = a;
		f = b;
		w = c;
		nxt = d;
	}
};
int src, sink;
int g[MAXM];
Edge e[MAXM];
struct node {
	int a, b, s;
} cs[MAXN];
int nume;
int a[MAXN][MAXN];
void addEdge(int u, int v, int c, int w) {
	printf("%d -> %d, flow: %d, cost: %d\n", u, v, c, w);
	e[++nume] = Edge(v, c, w, g[u]);
	g[u] = nume;
	e[++nume] = Edge(u, 0, -w, g[v]);
	g[v] = nume;
}
void init() {
	memset(g, 0, sizeof(g));
	nume = 1;

	int i, j;
	src = 0;
	sink = 2 * n + 1;
	for (i = 1; i <= n; i++) {
		addEdge(src, i, oo, 0);
		addEdge(i + n, sink, oo, 0);
		addEdge(i, i + n, cs[i].s / m + (cs[i].s % m != 0), 1);
	}
	for (i = 1; i <= n; i++) {
		for (j = 1; j <= n; j++) {
			if (cs[i].b + a[i][j] < cs[j].a) {
				addEdge(i + n, j, oo, -1);
			}
		}
	}
}
queue<int> q;
bool inq[MAXN];
int dist[MAXN];
int prev[MAXN], pree[MAXN];
bool findPath() {
	while (!q.empty()) {
		q.pop();
	}
	q.push(src);
	memset(dist, 63, sizeof(dist));
	dist[src] = 0;
	inq[src] = true;
	while (!q.empty()) {
		int u = q.front();
		q.pop();
		for (int i = g[u]; i; i = e[i].nxt) {
			if (e[i].f > 0 && dist[u] + e[i].w < dist[e[i].v]) {
				dist[e[i].v] = dist[u] + e[i].w;
				prev[e[i].v] = u;
				pree[e[i].v] = i;
				if (!inq[e[i].v]) {
					inq[e[i].v] = true;
					q.push(e[i].v);
				}
			}
		}
		inq[u] = false;
	}
	if (dist[sink] < oo) {
		return true;
	}
	return false;
}
int augment() {
	int u = sink;
	int delta = oo;
	while (u != src) {
		if (e[pree[u]].f < delta) {
			delta = e[pree[u]].f;
		}
		u = prev[u];
	}
	u = sink;
	while (u != src) {
		e[pree[u]].f -= delta;
		e[pree[u] ^ 1].f += delta;
		u = prev[u];
	}
	printf("%d %d\n", dist[sink], delta);
	return dist[sink] * delta;
}
int mincostflow() {
	int ans = 0;
	while (findPath()) {
		ans += augment();
	}
	return ans;
}
int main() {
	int T;
	int ca = 1;
	int i, j;
	scanf("%d", &T);
	while (T--) {
		scanf("%d%d", &n, &m);
		for (i = 1; i <= n; i++) {
			scanf("%d%d%d", &cs[i].a, &cs[i].b, &cs[i].s);
		}
		for (i = 1; i <= n; i++) {
			for (j = 1; j <= n; j++) {
				scanf("%d", &a[i][j]);
			}
		}
		init();
		printf("Case %d: %d\n", ca++, mincostflow());
	}
	return 0;
}
/*
 3
 1 5
 1 60 12
 0
 4 1
 1 100 10
 50 130 3
 150 200 15
 80 170 7
 0 2 3 4
 5 0 7 8
 9 10 0 12
 13 14 15 0
 2 1
 1 10 1
 12 20 1
 0 2
 5 0
 */