#include<bits/stdc++.h>
using namespace std;
const int maxn=1e2+10;
map<int,int> mp;
struct PP
{
    int pos;
    int pr;
    int im;
    int ma;
}node[maxn];
bool comp(PP a,PP b)
{
    if(a.ma!=b.ma)
    return a.ma<b.ma;
    return a.pos<b.pos;
}
int dp[100][40000+10];
int32_t main()
{
    int m,n; cin>>m>>n;
    int t1=0;
    int t2=0;
    for(int i=1;i<=n;i++)
    {
        node[i].pos=i;
        cin>>node[i].pr>>node[i].im>>node[i].ma;
        mp[node[i].ma]++;
        if(node[i].ma==0) t1++;
        else t2++;
    }
    sort(node+1,node+1+n,comp);
    for(int i=1;i<=n;i++)
    {
        node[i].im=node[i].pr*node[i].im;
    }
    int s=t1;
    for(int i=1;i<=s;i++)
    {
          if(mp[node[i].pos]>=0)
          {
              for(int j=m;j>=node[i].pr;j--)
              {
                  dp[i][j]=max(dp[i-1][j],dp[i][j]);
                  dp[i][j]=max(dp[i-1][j],dp[i-1][j-node[i].pr]+node[i].im);
              }
          }
          if(mp[node[i].pos]>=1)
          {

              t1++;
              for(int j=m;j>=node[i].pr+node[t1].pr;j--)
              {
                  //dp[i][j]=max(dp[i-1][j],dp[i][j]);
                  dp[i][j]=max(dp[i][j],dp[i-1][j-node[i].pr-node[t1].pr]+node[i].im+node[t1].im);
              }
          }
          if(mp[node[i].pos]>=2)
          {
              t1++;
              for(int j=m;j>=node[i].pr+node[t1].pr;j--)
              {
                  //dp[i][j]=max(dp[i-1][j],dp[i][j]);
                  dp[i][j]=max(dp[i][j],dp[i-1][j-node[i].pr-node[t1].pr]+node[i].im+node[t1].im);
              }
              for(int j=m;j>=node[i].pr+node[t1].pr+node[t1-1].pr;j--)
              {
                  //dp[i][j]=max(dp[i-1][j],dp[i][j]);
                  dp[i][j]=max(dp[i][j],dp[i-1][j-node[i].pr-node[t1].pr-node[t1-1].pr]+node[i].im+node[t1].im+node[t1-1].im);
              }
          }
    }cout<<dp[s][m];
}
//
4500 12
100 3 0
400 5 0
300 5 0
1400 2 0
500 2 0
800 2 4
1400 5 4
300 5 0
1400 3 8
500 2 0
1800 4 0
440 5 10
16700
//