#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
//  by zrt
//  problem:
//  无论你在什么时候开始，重要的是开始以后就不要停止。
using namespace std ;
typedef long long LL ;
const double eps(1e-10) ;
const int inf(0x3f3f3f3f) ;
int tt,kase;
int H[210],X[440000],P[440000],flow[440000],tot,from[440000],cost[440000];
inline void add(int x,int y,int z,int k){
	P[++tot]=y;X[tot]=H[x];H[x]=tot;flow[tot]=z;from[tot]=x;cost[tot]=k;
}
int mi[105],ni[105],pi[105],si[105],ei[105];
LL f,c;int S,T;
int d[210],a[210],p[210];
struct N{
	int x,w;
	N(int a=0,int b=0){
		x=a,w=b;
	}
	friend bool operator < (N a,N b){
		return a.w>b.w;
	}
};
priority_queue<N> q;
bool spfa(){
	memset(d,0x3f,sizeof d);
	d[S]=0;q.push(N(S,0));int x;
	a[S]=inf;
	while(!q.empty()){
		x=q.top().x;q.pop();
		for(int i=H[x];i;i=X[i]){
			if(flow[i]>0&&d[P[i]]>d[x]+cost[i]){
				d[P[i]]=d[x]+cost[i];
				a[P[i]]=min(flow[i],a[x]);
				p[P[i]]=i;
				q.push(N(P[i],d[P[i]]));
			}
		}
		while(!q.empty()&&d[q.top().x]!=q.top().w) q.pop();
	}
	if(d[T]>=0) return 0;
	f+=a[T];
	c+=a[T]*1LL*d[T];
	x=T;
	while(x!=S){
		flow[p[x]]-=a[T];
		flow[p[x]^1]+=a[T];
		x=from[p[x]];
	}
	return 1;
}
int main(){
	#ifdef LOCAL
	freopen("in.txt","r",stdin) ;
	freopen("out.txt","w",stdout) ;
	#endif
	scanf("%d",&tt);
	S=0,T=209;
	while(tt--){
		kase++;
		tot=1;memset(H,0,sizeof H);
		int m,I;
		scanf("%d%d",&m,&I);
		for(int i=1;i<=m;i++){
			scanf("%d%d%d%d%d",&mi[i],&ni[i],&pi[i],&si[i],&ei[i]);
		}
		for(int i=1;i<=m;i++){
			add(S,i<<1,ni[i],mi[i]);
			add(i<<1,S,0,-mi[i]);
			for(int j=0;j<=ei[i];j++){
				if(j+i>m) break;
				add(i<<1,(i+j)<<1|1,inf,I*j);
				add((i+j)<<1|1,i<<1,0,-I*j);
			}
			add(i<<1|1,T,si[i],-pi[i]);
			add(T,i<<1|1,0,pi[i]);
		}
		f=c=0;
		while(spfa());
		printf("Case %d: %lld\n",kase,-c);
	}
	return 0 ;
}