Problem Description

Our geometry princess XMM has stoped her study in computational geometry to concentrate on her newly opened factory. Her factory has introduced M new machines in order to process the coming N tasks. For the i-th task, the factory has to start processing it at or after day Si, process it for Pi days, and finish the task before or at day Ei. A machine can only work on one task at a time, and each task can be processed by at most one machine at a time. However, a task can be interrupted and processed on different machines on different days. 
Now she wonders whether he has a feasible schedule to finish all the tasks in time. She turns to you for help.

 

Input

On the first line comes an integer T(T<=20), indicating the number of test cases.

You are given two integer N(N<=500) and M(M<=200) on the first line of each test case. Then on each of next N lines are three integers Pi, Si and Ei (1<=Pi, Si, Ei<=500), which have the meaning described in the description. It is guaranteed that in a feasible schedule every task that can be finished will be done before or at its end day.

 

Output

For each test case, print “Case x: ” first, where x is the case number. If there exists a feasible schedule to finish all the tasks, print “Yes”, otherwise print “No”.

Print a blank line after each test case.

 

Sample Input

 

Sample Output

 

#include <stdio.h>

#include <bits/stdc++.h>

using namespace std;

#define INF 0x3f3f3f3f

#define CLR(arr,val) memset(arr,val,sizeof(arr))

#define LC(x) (x<<1)

#define RC(x) ((x<<1)+1)

#define MID(x,y) ((x+y)>>1)

typedef pair<int,int> pii;

typedef long long LL;

const double PI=acos(-1.0);

const int N=1010;

const int M=251000+7;

struct edge

{

    int to,nxt;

    int cap;

};

edge E[M<<1];

int head[N],tot,d[N];

void add(int s,int t,int cap)

{

    E[tot].to=t;

    E[tot].cap=cap;

    E[tot].nxt=head[s];

    head[s]=tot++;

    E[tot].to=s;

    E[tot].cap=0;

    E[tot].nxt=head[t];

    head[t]=tot++;

}

void init()

{

    CLR(head,-1);

    tot=0;

}

int bfs(int s,int t)

{

    CLR(d,-1);

    d[s]=0;

    queue<int>Q;

    Q.push(s);

    while (!Q.empty())

    {

        int now=Q.front();

        Q.pop();

        for (int i=head[now]; ~i; i=E[i].nxt)

        {

            int v=E[i].to;

            if(d[v]==-1&&E[i].cap>0)

            {

                d[v]=d[now]+1;

                if(v==t)

                    return 1;

                Q.push(v);

            }

        }

    }

    return d[t]!=-1;

}

int dfs(int s,int t,int f)

{

    if(s==t||!f)

        return f;

    int r=0;

    for (int i=head[s]; ~i; i=E[i].nxt)

    {

        int v=E[i].to;

        if(d[v]==d[s]+1&&E[i].cap)

        {

            int d=dfs(v,t,min(f,E[i].cap));

            if(d>0)

            {

                E[i].cap-=d;

                E[i^1].cap+=d;

                r+=d;

                f-=d;

                if(!f)

                    break;

            }

        }

    }

    if(!r)

        d[s]=INF;

    return r;

}

int dinic(int s,int t)

{

    int r=0;

    while (bfs(s,t))

        r+=dfs(s,t,INF);

    return r;

}

int main(void)

{

    int tcase,p,s,e,i,j,n,m;

    scanf("%d",&tcase);

    for (int q=1; q<=tcase; ++q)

    {

        init();

        scanf("%d%d",&n,&m);

        int S=0;

        int tl=INF,tr=-INF;

        int sump=0;

        for (i=1; i<=n; ++i)

        {

            scanf("%d%d%d",&p,&s,&e);

            add(S,i,p);

            sump+=p;

            if(s<tl)

                tl=s;

            if(e>tr)

                tr=e;

            for (j=s; j<=e; ++j)

                add(i,n+j,1);

        }

        int T=n+tr+1;

        for (i=tl; i<=tr; ++i)

            add(n+i,T,m);

        printf("Case %d: %s\n\n",q,dinic(S,T)==sump?"Yes":"No");

    }

    return 0;

}