#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<string> #include<vector> #include<queue> #include<cmath> #include<set> #include<memory.h> #include<set> using namespace std; int n,time,cnt; int dp[222][222]; int DP[400002]; struct Node { int x,y,v,t; }node[222]; void clear() { memset(node,0,sizeof(node)); memset(dp,0,sizeof(dp)); memset(DP,0,sizeof(DP)); cnt=0; } bool cmp(Node x,Node y) { if(x.x*y.y==y.x*x.y) return x.y<y.y; return y.x*x.y<x.x*y.y; } int main() { int Case=0; while(cin>>n>>time) { Case++; clear(); for(int i=0;i<n;i++) cin>>node[i].x>>node[i].y>>node[i].t>>node[i].v; sort(node,node+n,cmp); for(int i=0;i<222;i++) { dp[cnt][0]=0; dp[cnt][0]++; dp[cnt][dp[cnt][0]]=i; int tempx1=node[i].x; int tempy1=node[i].y; int tempa=node[i].t; int tempb=node[i].v; for(i++;i<222;i++) { int tempx2=node[i].x; int tempy2=node[i].y; tempa+=node[i].t; tempb+=node[i].v; if(tempy1*tempx2==tempy2*tempx1) { dp[cnt][0]++; dp[cnt][dp[cnt][0]]=i; node[i].t=tempa; node[i].v=tempb; } else { i--; break; } } cnt++; } for(int i=0;i<cnt;i++) { for(int j=time;j>=0;j--) { for(int k=1;k<=dp[i][0];k++) { if(j-node[dp[i][k]].t>=0) DP[j]=max(DP[j],DP[j-node[dp[i][k]].t]+node[dp[i][k]].v); } } } printf("Case %d: ",Case); cout<<DP[time]<<endl; } return 0; }