#include <iostream>
#include<cstdio>
#define maxn 32005
using namespace std;
int n,m,iw,ii,ib;
int w[maxn],c[maxn],bw[maxn][3],bc[maxn][3],dp[maxn];
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
    	scanf("%d%d%d",&iw,&ii,&ib);
        if(!ib){
            w[i]=iw;
            c[i]=iw*ii;
        }else{
            bw[ib][++bw[ib][0]]=iw;
            bc[ib][bw[ib][0]]=iw*ii;
        }
	}
    for(int i=1;i<=m;i++){
    	for(int j=n;w[i]!=0&&j>=w[i];j--){//类似零一背包，就是多考虑是否选附件 
            dp[j]=max(dp[j],dp[j-w[i]]+c[i]);
            if(j>=w[i]+bw[i][1])//考虑选附件1，就是现在的钱j够用 
                dp[j]=max(dp[j],dp[j-w[i]-bw[i][1]]+c[i]+bc[i][1]);
            if(j>=w[i]+bw[i][2])//考虑选附件2 
                dp[j]=max(dp[j],dp[j-w[i]-bw[i][2]]+c[i]+bc[i][2]);
            if(j>=w[i]+bw[i][1]+bw[i][2])//考虑都选 
                dp[j]=max(dp[j],dp[j-w[i]-bw[i][1]-bw[i][2]]+c[i]+bc[i][1]+bc[i][2]);
        }
	}
    printf("%d\n",dp[n]);
    return 0;
}