100分求条，玄关

#include <bits/stdc++.h>
using namespace std;
const int N = 4e4 + 5;
int dp[N];
int c[105];
int v[105];
vector<pair<int, int>> vec[105];

int main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int vi, wi, pi;
        cin >> vi >> wi >> pi;
        c[i] = vi;
        v[i] = vi * wi;
        if (pi == 0)
        {
            vec[i].push_back({c[i], v[i]});
        }
        else
        {
            int cnt = vec[pi].size();
            for (int j = 0; j < cnt; j++)
            {
                int new_c = c[i] + vec[pi][j].first;
                int new_v = v[i] + vec[pi][j].second;
                vec[pi].push_back({new_c, new_v});
            }
        }
    }
    for (int i = 1; i <= m; i++)
    {
        if (vec[i].size() == 0)
            continue;
        for (int j = n; j >= 0; j--)
        {
            for (int k = 0; k < vec[i].size(); k++)
            {
                if (j >= vec[i][k].first)
                {
                    dp[j] = max(dp[j], dp[j - vec[i][k].first] + vec[i][k].second);
                }
            }
        }
    }
    cout << dp[n];
    return 0;
}