Q3

#include <bits/stdc++.h>
typedef int_fast64_t lli;
using namespace std;

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

    lli C;
    cin >> C;

    lli Pf, Lf, Ps, Ls;
    cin >> Pf >> Lf;
    cin >> Ps >> Ls;

    lli N;
    cin >> N;

    function<lli(lli, vector<pair<lli, lli>>&)> knapsack = [](lli capacity, vector<pair<lli, lli>>& items)
    {
        vector<lli> dp(capacity + 1, 0);
        for(auto& item : items)
        {
            lli weight = item.first;
            lli value = item.second;
            for(lli j = capacity; j >= weight; j--)
            {
                if(dp[j - weight] + value > dp[j])
                {
                    dp[j] = dp[j - weight] + value;
                }
            }
        }
        return *max_element(dp.begin(), dp.end());
    };

    vector<tuple<lli, lli, lli>> items;
    for(lli i = 0; i < N; i++)
    {
        lli Vi, Ri, Wi;
        cin >> Vi >> Ri >> Wi;
        items.emplace_back(Vi, Ri, Wi);
    }

    vector<pair<lli, lli>> fast_items;
    for(auto& item : items)
    {
        lli Vi = get<0>(item);
        lli Ri = get<1>(item);
        lli Wi = get<2>(item);
        lli adjusted = Vi + Ri * Lf;
        if(adjusted > 0 && Wi <= C)
        {
            fast_items.emplace_back(Wi, adjusted);
        }
    }
    lli max_fast = knapsack(C, fast_items);
    lli profit_fast = max_fast - Pf;

    vector<pair<lli, lli>> slow_items;
    for(auto& item : items)
    {
        lli Vi = get<0>(item);
        lli Ri = get<1>(item);
        lli Wi = get<2>(item);
        lli adjusted = Vi + Ri * Ls;
        if(adjusted > 0 && Wi <= C)
        {
            slow_items.emplace_back(Wi, adjusted);
        }
    }
    lli max_slow = knapsack(C, slow_items);
    lli profit_slow = max_slow - Ps;

    cout << max(profit_fast, profit_slow) << "\n";

    return 0;
}