多重背包

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void (async function () {
    // Write your code here
    const arr1 = (await readline()).split(" ");
    const capacity = parseInt(arr1[0]);
    const n = parseInt(arr1[1]);
    const amounts = [];
    const weights = [];
    const values = [];
    for (let i = 0; i < n; i++) {
        let tokens = (await readline()).split(" ");
        amounts.push(parseInt(tokens[0]));
        weights.push(parseInt(tokens[1]));
        values.push(parseInt(tokens[2]));
    }
    const dp = new Array(capacity + 1).fill(0);
    for (let i = 0; i < n; i++) {
        if (weights[i] >= capacity) {
            zero_oneBP(1);
        }
        let k = 1;
        while (k <= amounts[i]) {
            zero_oneBP(k);
            amounts[i] -= k;
            k = k * 2;
        }

        if (amounts[i] > 0) zero_oneBP(amounts[i]);

        function zero_oneBP(k) {
            for (
                let remain_v = capacity;
                remain_v >= k * weights[i];
                remain_v--
            ) {
                let temp = k * values[i] + dp[remain_v - k * weights[i]];
                dp[remain_v] = Math.max(temp, dp[remain_v]);
            }
        }
    }
    console.log(dp[capacity]);
})();