main.cpp

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

using namespace std;

struct State {
    bool valid = false;
    int profit = 0;
    vector<int> counts;
};

bool better(const State& left, const State& right) {
    if (!right.valid) {
        return true;
    }
    if (left.profit != right.profit) {
        return left.profit > right.profit;
    }
    return lexicographical_compare(left.counts.begin(), left.counts.end(), right.counts.begin(), right.counts.end());
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, limit_h, limit_m;
    if (!(cin >> n >> limit_h >> limit_m)) {
        return 0;
    }
    vector<string> names(n);
    vector<int> hours(n), materials(n), profit(n);
    for (int i = 0; i < n; ++i) {
        cin >> names[i] >> hours[i] >> materials[i] >> profit[i];
    }
    vector<vector<State>> dp(limit_h + 1, vector<State>(limit_m + 1));
    dp[0][0].valid = true;
    dp[0][0].counts.assign(n, 0);

    for (int h = 0; h <= limit_h; ++h) {
        for (int m = 0; m <= limit_m; ++m) {
            if (!dp[h][m].valid) {
                continue;
            }
            for (int i = 0; i < n; ++i) {
                int nh = h + hours[i];
                int nm = m + materials[i];
                if (nh > limit_h || nm > limit_m) {
                    continue;
                }
                State candidate = dp[h][m];
                candidate.valid = true;
                candidate.profit += profit[i];
                candidate.counts[i] += 1;
                if (better(candidate, dp[nh][nm])) {
                    dp[nh][nm] = candidate;
                }
            }
        }
    }

    State best;
    best.valid = true;
    best.profit = 0;
    best.counts.assign(n, 0);
    for (int h = 0; h <= limit_h; ++h) {
        for (int m = 0; m <= limit_m; ++m) {
            if (dp[h][m].valid && better(dp[h][m], best)) {
                best = dp[h][m];
            }
        }
    }

    cout << "best_profit=" << best.profit << "\n";
    cout << "plan=";
    for (int i = 0; i < n; ++i) {
        if (i) {
            cout << ',';
        }
        cout << names[i] << ':' << best.counts[i];
    }
    cout << "\n";
    return 0;
}