WTRC's Memory

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<ctime>
#include<cstdlib>
#include<string>
#include<queue>
#include<cmath>
#include<set>
#include<map>
#include<bitset>
#define Rep(x,a,b) for (int x=a;x<=b;x++)
#define Drp(x,a,b) for (int x=a;x>=b;x--)
#define Cross(x,a) for (int x=head[a];~x;x=next[x])
#define ll long long
#define oo (1<<29)
#define mk(a,b) make_pair(a,b)
#define fr first
#define sc second
#define db double
using namespace std;
inline int IN(){
	int x=0,ch=getchar(),f=1;
	while (!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar();
	if (ch=='-'){f=-1;ch=getchar();}
	while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
	return x*f;
}
inline void OUT(ll x){
	if (x<0) putchar('-'),x=-x;
	if (x>=10) OUT(x/10),putchar(x%10+'0');
		else putchar(x+'0');
}
const int N=100005;
int n,c,d;
struct Machine{
	int d,r,p,g;
	bool operator <(const Machine&x)const{return g<x.g;}
}a[N];
ll dp[N];
int Cs,s[N],top;
db Y(int j,int k){
	db ret=dp[j]-dp[k]-a[j].p+a[k].p+a[j].r-a[k].r-1ll*a[j].g*(a[j].d+1)+1ll*a[k].g*(a[k].d+1);
	return ret;
}
db X(int j,int k){
	db ret=a[j].g-a[k].g;
	return ret;
}
int Get(db k){
	if (top==1) return 1;
	int l=1,r=top-1;
	if (Y(s[l+1],s[l])/X(s[l+1],s[l])<=k) return l;
	if (Y(s[r+1],s[r])/X(s[r+1],s[r])>=k) return r+1;
	while (l<r){
		int mid=l+r>>1;
		if (Y(s[mid+1],s[mid])/X(s[mid+1],s[mid])>=k) l=mid+1;
			else r=mid;
	}
	return l;
}
int main(){
	freopen("works.in","r",stdin);
	freopen("works.out","w",stdout);
	while (scanf("%d%d%d",&n,&c,&d)){
		if (!n&&!c&&!d) return 0;
		Rep(i,1,n) a[i].d=IN(),a[i].p=IN(),a[i].r=IN(),a[i].g=IN();
		a[n+1].d=d+1;
		sort(a+1,a+n+1);
		dp[0]=c;
		top=0,s[++top]=0;
		Rep(i,1,n+1){
			int j=Get((db)(-a[i].d));
			dp[i]=dp[s[j]]-a[s[j]].p+a[s[j]].r+1ll*a[s[j]].g*(a[i].d-a[s[j]].d-1);
			if (i==n+1) break;
			if (dp[i]>=a[i].p){
				while (top>1&&Y(i,s[top])/X(i,s[top])>=Y(s[top],s[top-1])/X(s[top],s[top-1])) top--;
				s[++top]=i;
			}
		}
		printf("Case %d: ",++Cs);OUT(dp[n+1]),putchar('\n');
	}
}