#include <bits/stdc++.h>
using namespace std;
int v[100],w[100],p[100];
int dp[320101];
int n,m;
int pl[100][3][3],p_cnt[100];
//pl[i][j][1]表示第i个物品的第j个附件的价值，pl[i][j][2]表示花费
//p_cnt[i]表示第i个物品有几个附件
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>w[i]>>v[i]>>p[i];v[i]*=w[i];
        if(p[i]>0){
            p_cnt[p[i]]++;
            pl[p[i]][p_cnt[p[i]]][1]=v[i];
            pl[p[i]][p_cnt[p[i]]][2]=w[i];
        }
    }
    for(int i=1;i<=m;i++){
        if(p[i]!=0)continue;
        if(p_cnt[i]==0){
            for(int j=n;j>=w[i];j--)dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
        }else if(p_cnt[i]==1){
            for(int j=n;j>=w[i];j--)dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
            for(int j=n;j>=w[i]+pl[i][1][2];j--)dp[j]=max(dp[j],dp[j-w[i]-pl[i][1][2]]+v[i]+pl[i][1][1]);
        }else{
            for(int j=n;j>=w[i];j--)dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
            for(int j=n;j>=w[i]+pl[i][1][2];j--)dp[j]=max(dp[j],dp[j-w[i]-pl[i][1][2]]+v[i]+pl[i][1][1]);
            for(int j=n;j>=w[i]+pl[i][2][2];j--)dp[j]=max(dp[j],dp[j-w[i]-pl[i][2][2]]+v[i]+pl[i][2][1]);
            for(int j=n;j>=w[i]+pl[i][1][2]+pl[i][2][2];j--)dp[j]=max(dp[j],dp[j-w[i]-pl[i][1][2]-pl[i][2][2]]+v[i]+pl[i][1][1]+pl[i][2][1]);
        }
    }cout<<dp[n];
    return 0;
}