#include <cstdio>

     #include <algorithm>

     #include <cstring>

     #include <iostream>

     #include <queue>

     #include <vector>

     using namespace std;

     typedef long long LL;

     const int maxn=+;

     const int maxm=+;

     const int INF=;

     struct MCMF{

         int head[maxn],to[maxm],Next[maxm],from[maxm],cost[maxm],flow[maxm],cap[maxm];

         int n,m,s,t,sz;

         int inq[maxn];

         int d[maxn];

         int p[maxn];

         int a[maxn];

         void init(int n){

             this->n=n;

             sz=-;

             memset(head,-,sizeof(head));

         }

         void AddEdge(int a,int b,int ca,int co){

             ++sz;

             to[sz]=b,from[sz]=a,Next[sz]=head[a],head[a]=sz;

             flow[sz]=,cap[sz]=ca,cost[sz]=co;

             ++sz;

             to[sz]=a,from[sz]=b,Next[sz]=head[b],head[b]=sz;

             flow[sz]=ca,cap[sz]=ca,cost[sz]=-co;

         }

         bool BellmanFord(int s,int t,int &Flow,LL &Cost){

             for(int i=;i<=n;i++)d[i]=INF;

             memset(inq,,sizeof(inq));

             d[s]=;inq[s]=;p[s]=-;a[s]=INF;

             queue<int>Q;

             Q.push(s);

             while(!Q.empty()){

                 int u=Q.front();Q.pop();

                 inq[u]=;

                 for(int i=head[u];i!=-;i=Next[i]){

                     int v=to[i];

                     if(cap[i]>flow[i]&&d[v]>d[u]+cost[i]){

                         d[v]=d[u]+cost[i];

                         p[v]=i;

                         a[v]=min(a[u],cap[i]-flow[i]);

                         if(!inq[v]){

                             Q.push(v);

                             inq[v]=;

                         }

                     }

                 }

             }

             if(d[t]==INF||d[t]>)return false;

             Flow+=a[t];

             Cost+=(LL)d[t]*(LL)a[t];

             int u=t;

             while(u!=s){

                 flow[p[u]]+=a[t];

                 flow[p[u]^]-=a[t];

                 u=from[p[u]];

             }

             return true;

         }

         LL Mincost(int s,int t){

             int Flow=;LL Cost=;

             while(BellmanFord(s,t,Flow,Cost));

             return Cost;

         }

     }mcmf;

     const int maxM=;

     int T,M,I,kase;

     int m[maxM],n[maxM],p[maxM],s[maxM],E[maxM];

     int main(){

         scanf("%d",&T);

        // freopen("out.txt","w",stdout);

         kase=;

         for(int t=;t<=T;t++){

             ++kase;

             scanf("%d%d",&M,&I);

             mcmf.init(*M+);

             mcmf.s=;mcmf.t=*M+;

             for(int i=;i<=M;i++){

                 scanf("%d%d%d%d%d",&m[i],&n[i],&p[i],&s[i],&E[i]);

                 mcmf.AddEdge(,i,n[i],m[i]);

                 mcmf.AddEdge(i+M,*M+,s[i],-p[i]);

                 for(int j=;j+i<=M&&j<=E[i];j++){

                     mcmf.AddEdge(i,i+j+M,INF,j*I);

                 }

             }

             LL ans=mcmf.Mincost(,*M+);

             printf("Case %d: %lld\n",kase,-ans);

         }

     return ;

     }