#include <bits/stdc++.h>
using namespace std;
#define TR(i,v)         for(__typeof((v).begin())i=(v).begin();i!=(v).end();++i)
#define DEBUG(x)        cout << #x << " = " << x << endl;
#define SIZE(p)         (int)(p).size()
#define MP(a, b)        make_pair((a), (b))
#define ALL(p)          (p).begin(), (p).end()
#define rep(i, n)       for(int (i)=0; (i)<(int)(n); ++(i))
#define REP(i, a, n)    for(int (i)=(a); (i)<(int)(n); ++(i))
#define FOR(i, a, b)    for(int (i)=(int)(a); (i)<=(int)(b); ++(i))
#define FORD(i, b, a)   for(int (i)=(int)(b); (i)>=(int)(a); --(i))
#define CLR(x, y)       memset((x), (y), sizeof((x)))
typedef long long LL;
typedef pair<int, int> pii;
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
const int INF = 1000000007;
class Network {
public:
    typedef int VAL;
    static const int SIZE = 505;
    typedef struct ARC{int t,c; VAL w; ARC* o;}* PTR;
    ARC arc[200005];
    PTR now[SIZE],e[SIZE]; 
    int cnt[SIZE],l[SIZE],r[SIZE],edge;
    VAL sum;
    void clear(){memset(e,edge=sum=0,sizeof(e));}
    ARC& REV(PTR x){return arc[(x-arc)^1];}    
    int flow(int S, int T){return improved_sap(S,T,INF);}    
    PTR add_edge(int x, int y, int c, VAL w = 0){
        e[x]=&(arc[edge++]=(ARC){y,c,+w,e[x]});
        e[y]=&(arc[edge++]=(ARC){x,0,-w,e[y]});
        return e[x];
    }          
    int aug(int S, int T, int& can){
        int x,z=T,use=can;
        for(x=S;x!=T;x=now[x]->t) if(use>now[x]->c) use=now[z=x]->c;
        for(x=S;x!=T;x=now[x]->t){
                now[x]->c-=use;
            REV(now[x]).c+=use;
            sum+=use*now[x]->w;
        }
        can-=use;
        return z;
    }    
    int improved_sap(int S, int T, int can){
        if(S==T) return can;
        int in=can,x,m;
        memcpy(now,e,sizeof(now));
        memset(cnt,0,sizeof(cnt));
        fill_n(l,SIZE,int(SIZE));
        for(int i=m=l[r[0]=T]=0;i<=m;i++){
            cnt[l[x=r[i]]]++;
            for(PTR u=e[x];u;u=u->o)
                if(l[u->t]==SIZE && REV(u).c) l[r[++m]=u->t]=l[x]+1;
        }
        for(x=r[S]=S;l[S]!=SIZE;x=r[x]){
        JMP:for(PTR& u=now[x];u;u=u->o) if(l[u->t]<l[x] && u->c){
                r[u->t]=x;
                x=u->t==T?aug(S,T,can):u->t;
                if(x==T) return in; else goto JMP;
            }
            if(!--cnt[l[x]]) break; else l[x]=SIZE;
            for(PTR u=e[x];u;u=u->o)
                if(l[u->t]+1<l[x] && u->c) now[x]=u,l[x]=l[u->t]+1;
            if(l[x]!=SIZE) cnt[l[x]]++;
        }
        return in-can;
    }        
}solver;
const int maxn = 105;
int startT[maxn], endT[maxn], S[maxn],Clean[maxn][maxn];
inline bool okok(int i,int j) {
	return startT[j]-endT[i] > Clean[i][j];
}
int main(int argc, char const *argv[]) {
#ifndef ONLINE_JUDGE
    freopen("B.in", "r", stdin);
    // freopen("out", "w", stdout);
#endif
    // ios::sync_with_stdio(false);		cin.tie(0);
	int T;	scanf("%d", &T);
	FOR(cs,1,T) {
		printf("Case %d: ",cs);
		int n,m;	scanf("%d%d", &n,&m);
		rep(i,n)	scanf("%d%d%d", startT+i,endT+i,S+i), S[i]=(S[i]+m-1)/m;
		rep(i,n)	
		rep(j,n)	scanf("%d",Clean[i]+j);		
		int sr=n+n,sk=n+n+1,s=n+n+2,t=n+n+3;		
		int l=0, r=accumulate(S,S+n,0),fsum=r;				
		while(l<r) {
			int mid=(l+r)>>1;
			solver.clear();
			rep(i,n)
				solver.add_edge(sr,i,S[i]), solver.add_edge(i+n,sk,S[i]),
				solver.add_edge(i,s,INF),solver.add_edge(t,i+n,INF) ;
			rep(i,n)
			rep(j,n) if(i!=j && okok(i,j)) {				
				solver.add_edge(i,j+n,INF);
			}
			solver.add_edge(s,t,mid);
			int f=solver.flow(sr,sk);			
			if(f==fsum)	r=mid;
			else 		l=mid+1;
		}
		printf("%d\n",l);
	}
    return 0;
}