Gold Miner - Accepted

/*
    http://acm.tju.edu.cn/toj/showp3906.html
*/

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <bitset>

using namespace std;

#define DIM 205

int N, T, mx;

int dp[DIM * DIM];

struct gold {
    int x, y, time, value;
} V[DIM];

bool cmp(gold a, gold b);

int main() {
    #ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    #endif // ONLINE_JUDGE

    int Case = 1;

    while(scanf("%d %d\n", &N, &T) != EOF) {
        for(int i = 1; i <= N; ++i) {
            scanf("%d %d %d %d\n", &V[i].x, &V[i].y, &V[i].time, &V[i].value);
        }

        sort(V + 1, V + 1 + N, cmp);

        memset(dp, 0, sizeof(dp));

        int last, mx = 0;

        for(int first = 1; first <= N; ++first) {
            last = first;

            while(last <= N && (V[first].x * V[last].y - V[first].y * V[last].x) == 0) {
                ++last;
            }

            for(int i = T; i; --i) {
                int sum = 0, time = 0;

                for(int j = first; j < last; ++j) {
                    sum += V[j].value;
                    time += V[j].time;

                    if(i >= time && (dp[i - time] > 0 || i == time)) {
                        dp[i] = max(dp[i], dp[i - time] + sum);
                    }
                }
            }

            first = last - 1;
        }

        mx = 0;

        for(int i = 0; i <= T; ++i) {
            mx = max(mx, dp[i]);
        }

        cout << "Case " << Case << ": " << mx << '\n';
        ++Case;
    }

    return 0;
}

bool cmp(gold a, gold b) {
    if(a.x * b.y - a.y * b.x == 0) {
        return a.y < b.y;
    }

    return (a.x * b.y - a.y * b.x) > 0;
}