非常经典的一道分组背包问题，比较要注意的是组内互斥不要忘了，板子题

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
typedef pair<int, int> PII;

const int mod = 1e9 + 7, MOD = 998244353;
const int N = 65, inf = 0x3f3f3f3f, INF = 0x3f3f3f3f3f3f3f3f;

int n, m, dp[32005];
int w[N], val[N];
bool king[N];
vector<int> h[N];

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

  cin >> m >> n;

  int c, bel;
  for (int i = 1; i <= n; i++)
    {
      cin >> w[i] >> c >> bel;
      val[i] = w[i] * c;
      if (!bel)
        king[i] = true;
      else
        h[bel].emplace_back(i);
    }
  for (int i = 1; i <= n; i++)
    if (king[i])
      for (int j = m; j; j--)
        {
          if (j >= w[i])
            dp[j] = max(dp[j], dp[j - w[i]] + val[i]);
          if (h[i].size() == 2)
            {
              int _w = w[i] + w[h[i][0]] + w[h[i][1]];
              if (j >= _w)
                dp[j] = max(dp[j],
                            dp[j - _w] + val[i] + val[h[i][0]] + val[h[i][1]]);
            }
          for (int it : h[i])
            {
              if (j >= w[i] + w[it])
                dp[j] = max(dp[j], dp[j - w[i] - w[it]] + val[i] + val[it]);
            }
        }

  cout << dp[m];

  return 0;
}