/* ***********************************************Author        :devil************************************************ */#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#include <vector>#include <queue>#include <set>#include <stack>#include <map>#include <string>#include <cmath>#include <stdlib.h>#define inf 0x3f3f3f3f#define LL long long#define rep(i,a,b) for(int i=a;i<=b;i++)#define dec(i,a,b) for(int i=a;i>=b;i--)#define ou(a) printf("%d\n",a)#define pb push_back#define mkp make_pairtemplate<class T>inline void rd(T &x){char c=getchar();x=0;while(!isdigit(c))c=getchar();while(isdigit(c)){x=x*10+c-‘0‘;c=getchar();}}#define IN freopen("in.txt","r",stdin);#define OUT freopen("out.txt","w",stdout);using namespace std;const int mod=1e9+7;const int N=1e5+10;int t,n,m;#define maxm 500010#define maxn 222int a[maxn],b[maxn],s[maxn],all;int head[maxn],eid;int dis[maxn];//残量网络中节点i到汇点t的最短距离int num[maxn];//和t的最短距离等于i的节点数量int cur[maxn];//当前弧下标int pre[maxn];//可增广路上的上一条弧的编号struct node{    int v,cap,next;} edge[maxm];void add(int u,int v,int cap){    edge[eid].v=v;    edge[eid].cap=cap;    edge[eid].next=head[u];    head[u]=eid++;    edge[eid].v=u;    edge[eid].cap=0;    edge[eid].next=head[v];    head[v]=eid++;}void bfs(int source,int sink)//预处理，利用反向BFS，更新dis数组{    queue<int>q;    while(!q.empty()) q.pop();    memset(num,0,sizeof(num));    memset(dis,-1,sizeof(dis));    q.push(sink);    dis[sink]=0;    num[0]=1;    while(!q.empty())    {        int u=q.front();        q.pop();        for(int i=head[u]; i!=-1; i=edge[i].next)        {            int v=edge[i].v;            if(dis[v]==-1)            {                dis[v]=dis[u]+1;//找允许弧                num[dis[v]]++;                q.push(v);            }        }    }}int isap(int source,int sink,int n)//n为残量网络中的节点到汇点的最大距离，通常节点的个数，即上限{    memcpy(cur,head,sizeof(cur));    int flow=0,u=pre[source]=source;    bfs(source,sink);//更新dis数组    while(dis[source]<n)    {        if(u==sink)        {            int df=inf,pos;            for(int i=source;i!=sink;i=edge[cur[i]].v)//追踪增广路路径，最小残量df            {                if(df>edge[cur[i]].cap)                {                    df=edge[cur[i]].cap;                    pos=i;                }            }            for(int i=source;i!=sink;i=edge[cur[i]].v)//更新流量            {                edge[cur[i]].cap-=df;                edge[cur[i]^1].cap+=df;            }            flow+=df;            u=pos;        }        int st;        for(st=cur[u];st!=-1;st=edge[st].next)//从当前弧开始查找允许弧            if(dis[edge[st].v]+1==dis[u]&&edge[st].cap)//找到允许弧跳出                break;        if(st!=-1)        {            cur[u]=st;            pre[edge[st].v]=u;            u=edge[st].v;        }        else        {            if((--num[dis[u]])==0) break;//GAP优化,出现断层结束            int mind=n;            for(int id=head[u];id!=-1;id=edge[id].next)//retreat操作：更新dis数组            {                if(mind>dis[edge[id].v]&&edge[id].cap)                {                    cur[u]=id;//修改标号的同时修改当前弧                    mind=dis[edge[id].v];                }            }            dis[u]=mind+1;            num[dis[u]]++;            if(u!=source) u=pre[u];// 回溯继续寻找允许弧        }    }    return flow;}void init(){    memset(head,-1,sizeof(head));    eid=0;    all=0;}int main(){    rd(t);    rep(y,1,t)    {        init();        rd(n),rd(m);        rep(i,1,n) rd(a[i]),rd(b[i]),rd(s[i]);        rep(i,1,n)        {            int w=s[i]/m;            if(s[i]%m) w++;            all+=w;            add(0,i,w);            add(i+n,n*2+1,w);        }        rep(i,1,n) rep(j,1,n)        {            rd(m);            if(b[i]+m<a[j]) add(i,j+n,inf);        }        printf("Case %d: %d\n",y,all-isap(0,2*n+1,n));    }    return 0;}