题意：

有N节课，每节课有起止时间和学生数

然后给你M是每个教室容纳的学生数

然后给你n*n的矩阵表示上完第i节课然后上第j节课需要a[i][j]的时间调整

第i节课结束时间加上调整时间要严格小于第j节课的开始时间

问你最少需要多少个教室

思路：

很简单的一个最大流

每节课分为两个节点，0为超级源点，2*n+1为超级汇点

先算出每节课需要的教室数，加到all里

然后从0到1-n加一个流量为教室数的边

从n+1——2*n到2*n+1加一个流量为教室数的边

然后将满足条件的i和j课程，从i到j+n连一条流量为inf的边

答案就是all-最大流

/* ***********************************************
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_pair
template<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 222
int 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;
}