#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <bits/stdc++.h>
#define debug(x) cout<<#x<<" = "<<x<<endl
#define FOR(i,l,r) for (int i=(l);i<=(r);i++)
#define FORD(i,r,l) for (int i=(r);i>=(l);i--)
using namespace std;
const int maxn=205+1,maxm=120000,jx=0x7fffffff;

int pos,ta[maxn],lin[maxm],sd[maxm],sl[maxm];
void biu(int s,int t,int c)
{
    ++pos; lin[pos]=ta[s]; ta[s]=pos; sd[pos]=t; sl[pos]=c;
    ++pos; lin[pos]=ta[t]; ta[t]=pos; sd[pos]=s; sl[pos]=0;
}

int nn;
int h[maxn];
int vh[maxn];
int aug(int v,int deta)
{
    if (v==nn) return deta;
    int mins=nn-1,augc,bak=deta;
    for (int i=ta[v];i;i=lin[i])
        if (sl[i])
        {
            if (h[v]==h[sd[i]]+1)
            {
                augc=min(deta,sl[i]);
                augc=aug(sd[i],augc);
                deta-=augc;
                sl[i]-=augc; sl[(i+1^1)-1]+=augc;
                if (!deta) break;
                if (h[nn-1]>=nn) return bak-deta;
            }
            mins=min(mins,h[sd[i]]);
        }
    if (bak==deta)
    {
        vh[h[v]]--; if (vh[h[v]]==0) h[nn-1]=nn;
        h[v]=mins+1; vh[h[v]]++;
    }
    return bak-deta;
}

int n,m;
int A[101],B[101],S[101];
int clean[101][101];
int rd[101*2],cd[101*2];
void init(int nn)
{
    pos=0;
    for (int i=0;i<=nn;i++) ta[i]=h[i]=vh[i]=0;
    for (int i=1;i<=n*2;i++) rd[i+n]=cd[i]=0;
}
void make_graph()
{
    init(n*2+4);
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
            if (B[i]+clean[i][j]<A[j])//?
                biu(i+n,j,jx);
    nn=n*2+2;
    for (int i=1;i<=n;i++) biu(nn-1,i,jx),biu(i+n,nn,jx);
    for (int i=1;i<=n;i++)
    {
        rd[i+n]+=(S[i]-1)/m+1;
        cd[i]+=(S[i]-1)/m+1;
        biu(i,i+n,jx);
    }

    nn+=2;
    for (int i=1;i<=n;i++) biu(i,nn,cd[i]),biu(nn-1,i+n,rd[i+n]);
}
int solve()
{

    int sum=0,flow=0;
    make_graph();
    while (h[nn-1]<nn) flow+=aug(nn-1,jx);
    for (int i=1;i<=n;i++) sum+=cd[i];
    if (sum!=flow)
    {
        memset(h,0,sizeof(h));
        memset(vh,0,sizeof(vh));
        biu(nn-2,nn-3,jx);
        while (h[nn-1]<nn) aug(nn-1,jx);
    }
    int ans=0;
    nn-=2;
    for (int i=ta[nn-1];i;i=lin[i])
        if (sd[i]==nn)
        {
            ans=sl[i];
            break;
        }
    return ans;
}
int main(){
    for (int T;scanf("%d",&T)!=EOF;)
        for (int tt=1;T--;tt++)
        {
            scanf("%d%d",&n,&m);
            for (int i=1;i<=n;i++) scanf("%d%d%d",A+i,B+i,S+i);
            for (int i=1;i<=n;i++)
                for (int j=1;j<=n;j++) scanf("%d",&clean[i][j]);
            printf("Case %d: %d\n",tt,solve());
        }
    return 0;
}