WA 飞了

思路是建图后 $dis_t\ge0$ 就退出。

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#include <stdio.h>
#include <string.h> 
#include <algorithm>
#include <queue>
#include <math.h>
#define od(x) printf("%d",x)
#define odb(x) printf("%d ",x)
#define odl(x) printf("%d\n",x)
#define odp(x,y) printf("%d %d\n",x,y)
#define ol(x) puts("")
#define old(x) printf("%lld",x)
#define oldb(x) printf("%lld ",x)
#define oldl(x) printf("%lld\n",x)
#define oldp(x,y) printf("%lld %lld\n",x,y)
#define rg(x) for(int i=1;i<=(x);i++){
#define rg_(i,x) for(int i=1;i<=(x);i++){
#define gr }
#define rrg(x) for(int i=0;i<(x);i++)
#define rdln(a) a[i]=read();
#define rdln0(a,x) rrg(x) rdln(a) gr
#define rdln1(a,x) rg(x) rdln(a) gr
#define int long long
inline int read()
{
	int num=0,f=1;char c=getchar();
	while(c<48||c>57){if(c=='-')f=-1;c=getchar();}
	while(c>47&&c<58)num=num*10+(c^48),c=getchar();
	return num*f;
}
inline int min(int a,int b){return a>b?b:a;}
inline int max(int a,int b){return a<b?b:a;}
struct Edge{
	int v,w,nxt,c;
}e[1000005];
int h[100005],cnt=2;
int a[200005],vv;
inline void addedge(int u,int v,int w,int c)
{//	if(w)oldb(u),oldb(v),printf("%lld,%lld\n",w,c);
	e[cnt]=(Edge){v,w,h[u],c};
	h[u]=cnt++;
}
int dis[100005],cur[100005],inq[100005];
inline bool devin(int s,int t)
{
	memset(dis,0x3f,sizeof(dis));
	memcpy(cur,h,sizeof(cur));
	int inf=dis[0];
	std::queue<int>q;
	q.push(s);dis[s]=0;
	while(!q.empty())
	{
		int u=q.front();q.pop();
		inq[u]=0;
		for(int i=h[u];i;i=e[i].nxt)
		{
			int v=e[i].v;
			if(e[i].w&&dis[v]>dis[u]+e[i].c)
			{
				dis[v]=dis[u]+e[i].c;
				if(!inq[v])
				{
					inq[v]=1;
					q.push(v);
				}
			}
		}
	}
	return dis[t]!=inf;
}
#define vis inq
int dfs(int u,int t,int flow,int& cost)
{
	if(u==t)return flow;
	vis[u]=1;
	int ans=0;
	for(int& i=cur[u];i&&ans<flow;i=e[i].nxt)
	{
		int v=e[i].v;
		if(!vis[v]&&e[i].w&&dis[v]==dis[u]+e[i].c)
		{
			int fl=dfs(v,t,min(e[i].w,flow-ans),cost);
			if(fl)cost+=fl*e[i].c,e[i].w-=fl,e[i^1].w+=fl,ans+=fl;
		}
	}
	vis[u]=0;
	return ans;
}
const int qwq=(1<<31)-1;
inline void pig(int u,int v,int w,int c)
{
//printf("                 ");	oldb(u),oldp(v,w);
	addedge(u,v,w,c);
	addedge(v,u,0,-c);
}
int fl[114514];
int n,m,s,t,S,T,flow,mincost;
inline void add(int u,int v,int l,int r,int c)
{
	pig(u,v,r-l,c);
	fl[u]-=l;
	fl[v]+=l;
	mincost+=c*l;
}
const int inf=0x3f3f3f3f;
signed main()
{
	int n=0;read();int Case=0;
	while(-1!=scanf("%lld",&n)){memset(h,0,sizeof(h));cnt=2;
	if(n==0)return 0;
	int m=read();
	int s=0,t=n+n+1;
//	rg(n+1)pig(i-1,i,inf,m);gr
	rg(n)int cost=read(),maxn=read(),unitsell=read(),maxsell=read(),keep=read();
	for(int j=i;j<=n&&j<=i+keep;j++)pig(i,j+n,inf,(j-i)*m);
	pig(s,i,maxn,cost);
	pig(i+n,t,maxsell,-unitsell);
	gr
//	return 0;
	int flow,maxsell=0;
	while(devin(s,t))
	{
		if(dis[t]>=0)break;
		qwq:;
		int x=dfs(s,t,0x3f3f3f3f,mincost);
		if(x==0)continue;
		goto qwq;
	}
	printf("Case %lld: %lld\n",++Case,-mincost);
	gr
}