#include<bits/stdc++.h>
using namespace std;
int m;
int n;
int zvw[100][2];
int fv[100][2];
int fw[100][2];
int dp[61][50000];
int solve(int zm)
{
    for(int i=1;i<=zm;i++){
        for(int j=n;j>=zvw[i][0];j--){
            dp[i][j]=max(dp[i-1][j],dp[i-1][j-fv[i][0]]+fw[i][1]);
            if(j>zvw[i][0]+fv[i][0])dp[i][j]=max(dp[i][j],dp[i-1][j-zvw[i][0]-fv[i][0]]+zvw[i][1]+fw[i][0]);
            if(j>zvw[i][0]+fv[i][1])dp[i][j]=max(dp[i][j],dp[i-1][j-zvw[i][0]-fv[i][1]]+zvw[i][1]+fw[i][1]);
            if(j>=zvw[i][0]+fv[i][0]+fv[i][1])dp[i][j]=max(dp[i][j],dp[i-1][j-zvw[i][0]-fv[i][0]-fv[i][1]]+zvw[i][1]+fw[i][0]+fw[i][1]);
        }
    }
    return dp[zm][n];
}
int main()
{
    cin>>n>>m;
    int cnt=0,cn=0;
    for(int i=1;i<=m;i++){
        int v,p,q;
        cin>>v>>p>>q;
        p*=v;
        if(q==0){
            cnt++;
            cn=0;
            zvw[cnt][0]=v;
            zvw[cnt][1]=p;
        }
        else {
            fv[q][cn]=v;
            fw[q][cn]=p;
            cn++;
        }
    }
    cout<<solve(cnt);
    return 0;
}