#include<bits/stdc++.h> using namespace std; const int N=35000; int dp[N];

struct point{

int v1,v2,v3;

int s1,s2,s3; }p[N];

int main() {

int i,j,n,m,v,nums,q;

cin>>n>>m;

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

  cin>>v>>q>>nums;
  
  if(nums==0){
     p[i].v1=v;
     
     p[i].s1=v*q;
  }
  
  else{
  	
     if(p[nums].v2==0){
     	
        p[nums].v2=v;
        
        p[nums].s2=v*q;
     }
     
     else{
     	
        p[nums].v3=v;
        
        p[nums].s3=v*q;
        
     }
     
  }

} for(i=1;i<=m;i++){

  for(j=n;j>=1;j--){
  	
     if(p[i].v1<=j){
     	
        dp[j]=max(dp[j],dp[j-p[i].v1]+p[i].s1);
     }
     
     if(p[i].v1+p[i].v2<=j){
     	
        dp[j]=max(dp[j],dp[j-p[i].v1-p[i].v2]+p[i].s1+p[i].s2);
     }
      if(p[i].v1+p[i].v3<=j){
      	
        dp[j]=max(dp[j],dp[j-p[i].v1-p[i].v3]+p[i].s1+p[i].s3);
     }
     
      if(p[i].v1+p[i].v2+p[i].v3<=j){
      	
        dp[j]=max(dp[j],dp[j-p[i].v1-p[i].v2-p[i].v3]+p[i].s1+p[i].s2+p[i].s3);
     }
     
  }

}

cout<<dp[n]; return 0; }