#include<iostream>

#include<algorithm>

#include<vector>

using namespace std;

int n,m;

int dp[];

int v[],p[];

vector<int> appv[],appp[];

int main(){

    cin>>n>>m;

    for(int i=;i<=m;i++){

        int a,b,c;

        cin>>a>>b>>c;

        if(!c){

            v[i]=a;

            p[i]=b;

        }

        else{

            appv[c].push_back(a);

            appp[c].push_back(b);

        }

    }

    for(int i=;i<=m;i++){

        if(p[i]!=){

            for(int j=n;j>=v[i];j--){

                dp[j]=max(dp[j],dp[j-v[i]]+v[i]*p[i]);

                if(appv[i].size()==){

                    if(j>=appv[i][]+v[i]){

                        dp[j]=max(dp[j],dp[j-appv[i][]-v[i]]+appv[i][]*appp[i][]+v[i]*p[i]);

                    }

                }

                else if(appv[i].size()==){

                    if(j>=appv[i][]+v[i]+appv[i][]){

                        dp[j]=max(dp[j],dp[j-appv[i][]-v[i]-appv[i][]]+appv[i][]*appp[i][]+v[i]*p[i]+appv[i][]*appp[i][]);

                    }

                    if(j>=appv[i][]+v[i]){

                        dp[j]=max(dp[j],dp[j-appv[i][]-v[i]]+appv[i][]*appp[i][]+v[i]*p[i]);

                    }

                    if(j>=appv[i][]+v[i]){

                        dp[j]=max(dp[j],dp[j-appv[i][]-v[i]]+appv[i][]*appp[i][]+v[i]*p[i]);

                    }

                }

            }

        }

    }

    cout<<dp[n]<<endl;

    return ;

}