#include<bits/stdc++.h>

#define N 10005

#define inf 1000000007

#define naive 0

using namespace std;

typedef long long ll;ll ans=naive;

int wy,n,m,I,head[N],tot=naive,pre[N],inq[N],dis[N],s,t;

struct Edge{int u,v,next,f,c;}G[];

inline void addedge(int u,int v,int f,int c){

    G[tot].u=u;G[tot].v=v;G[tot].f=f;G[tot].c=c;G[tot].next=head[u];head[u]=tot++;

    G[tot].u=v;G[tot].v=u;G[tot].f=;G[tot].c=-c;G[tot].next=head[v];head[v]=tot++;

}

inline bool bfs(int s,int t){

    memset(inq,naive,sizeof(inq));memset(pre,-,sizeof(pre));for(int i=s;i<=t;i++)dis[i]=inf;

    queue<int>q;q.push(s);dis[s]=naive;

    while(!q.empty()){

        int u=q.front();q.pop();inq[u]=;

        for(int i=head[u];~i;i=G[i].next){

            int v=G[i].v,f=G[i].f,c=G[i].c;

            if(f&&dis[v]>dis[u]+c){pre[v]=i;dis[v]=dis[u]+c;inq[v]=;q.push(v);}

        }

    }

    return dis[t]!=inf;

}

void mcmf(int s,int t){

    while(bfs(s,t)){

        int x=inf;if(dis[t]>)return;

        for(int i=pre[t];~i;i=pre[G[i].u])x=min(x,G[i].f);

        for(int i=pre[t];~i;i=pre[G[i].u])G[i].f-=x,G[i^].f+=x,ans+=1LL*G[i].c*x;

    }

}

inline int read(){

    int f=,x=;char ch;

    do{ch=getchar();if(ch=='-')f=-;}while(ch<''||ch>'');

    do{x=x*+ch-'';ch=getchar();}while(ch>=''&&ch<='');

    return f*x;

}

int main(){

    int T=read();

    while(T--){

        m=read();I=read();ans=naive;memset(head,-,sizeof(head));tot=naive;t=*m+;s=naive;

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

            int c1=read(),f1=read(),c2=read(),f2=read(),x=read();

            addedge(s,i,f1,c1);addedge(i+m,t,f2,-c2);

            for(int j=i;j<=min(i+x,m);j++)addedge(i,j+m,inf,I*(j-i));

        }

        mcmf(s,t);printf("Case %d: %lld\n",++wy,-ans);

    }

}