#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;
}

  cin>>v>>q>>nums;
  
  if(nums==0){
     p[i].v1=v;
     
     p[i].s1=v*q;
  }
  
  else{
  	
     if(p[nums].v2==0){
     	
        p[nums].v2=v;
        
        p[nums].s2=v*q;
     }
     
     else{
     	
        p[nums].v3=v;
        
        p[nums].s3=v*q;
        
     }
     
  }

  for(j=n;j>=1;j--){
  	
     if(p[i].v1<=j){
     	
        dp[j]=max(dp[j],dp[j-p[i].v1]+p[i].s1);
     }
     
     if(p[i].v1+p[i].v2<=j){
     	
        dp[j]=max(dp[j],dp[j-p[i].v1-p[i].v2]+p[i].s1+p[i].s2);
     }
      if(p[i].v1+p[i].v3<=j){
      	
        dp[j]=max(dp[j],dp[j-p[i].v1-p[i].v3]+p[i].s1+p[i].s3);
     }
     
      if(p[i].v1+p[i].v2+p[i].v3<=j){
      	
        dp[j]=max(dp[j],dp[j-p[i].v1-p[i].v2-p[i].v3]+p[i].s1+p[i].s2+p[i].s3);
     }
     
  }