Panic at the bakery 2

A local bakery is going to make buns and sell them.

However, because of the high cost of flour, they cannot afford a whole lot of flour. They can only use amount of flour they have left.

For each bun, they can add a stuffing. They have stuffing types and the amounts of the stuffings is also limited. (the stuffing has only grams left)

To make each bun with stuffing, it takes grams of stuffing and grams of flour. The bun with stuffing can be sold to Rs amount.

However, unlike last time, now they know how to make buns without any stuffing. So if they chose to make plain buns without any stuffing, it would take grams of flour and can be sold to amount.

Find the maximum amount that the bakery can earn.

Input Format

First line contains , , and . Next lines contains , , and corresponding to the stuffing.

Constraints

Output Format

Output a single number containing the maximum amount that the bakery can earn.

Sample Input 0

100 2 20 10
70 30 20 1000
120 30 10 100

Sample Output 0

2410

Explanation 0

Here the best approach would be to bake,

• 2 buns from stuffing 1 - earn Rs 2000, uses 60g (out of 70g) of stuffing and 40g of flour
• 4 buns from stuffing 2 - earn Rs 400, uses 120g (out of 120g) of stuffing and 40g of flour
• 1 bun without stuffing - earn Rs 10, uses 20g of flour (out of 20g flour remaining)

Total earned = Rs 2410

Solution

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

using namespace std;

struct Bun {
    int stuffing_id;
    int flour_per_bun;
    int stuffing_per_bun;
    int value_per_bun;
    double value_per_flour;
};

int main() {
    int flour, n, plain_flour, plain_value;
    cin >> flour >> n >> plain_flour >> plain_value;

    vector<int> stuffing_left(n);
    vector<Bun> buns;

    for (int i = 0; i < n; ++i) {
        int stuffing_amt, stuffing_use, flour_use, value;
        cin >> stuffing_amt >> stuffing_use >> flour_use >> value;

        stuffing_left[i] = stuffing_amt;
        Bun b;
        b.stuffing_id = i;
        b.stuffing_per_bun = stuffing_use;
        b.flour_per_bun = flour_use;
        b.value_per_bun = value;
        b.value_per_flour = (double)value / flour_use;
        buns.push_back(b);
    }

    // Add plain bun
    Bun plain;
    plain.stuffing_id = -1;
    plain.stuffing_per_bun = 0;
    plain.flour_per_bun = plain_flour;
    plain.value_per_bun = plain_value;
    plain.value_per_flour = (double)plain_value / plain_flour;
    buns.push_back(plain);

    // Sort buns by value per flour (descending)
    sort(buns.begin(), buns.end(), [](const Bun &a, const Bun &b) {
        return a.value_per_flour > b.value_per_flour;
    });

    int total_earned = 0;

    for (auto &bun : buns) {
        int max_buns_by_flour = flour / bun.flour_per_bun;
        int max_buns_by_stuffing = INT32_MAX;

        if (bun.stuffing_id != -1) {
            max_buns_by_stuffing = stuffing_left[bun.stuffing_id] / bun.stuffing_per_bun;
        }

        int buns_to_make = min(max_buns_by_flour, max_buns_by_stuffing);
        total_earned += buns_to_make * bun.value_per_bun;
        flour -= buns_to_make * bun.flour_per_bun;

        if (bun.stuffing_id != -1) {
            stuffing_left[bun.stuffing_id] -= buns_to_make * bun.stuffing_per_bun;
        }
    }

    cout << total_earned << endl;
    return 0;
}