#include<bits/stdc++.h>

using namespace std;

int m,n,w[1005],c[1005],p[1005],dp[1010][1010];

signed main(){

cin>>m>>n;

for(int i=1;i<=n;i++)

{

	cin>>w[i]>>c[i]>>p[i];

}

for(int i=1;i<=n;i++)

{

	for(int j=1;j<=m;j++)

	{

		dp[i][j]=dp[i-1][j];
  
		if(j>=w[i]){
  
			if(p[i]==0)dp[i][j]=max(dp[i-1][j],dp[i][j-w[i]]+c[i]);
    
			else {
    
				for(int k=1;k<=p[i]&&k*w[i]<=j;k++)
				{
      
					dp[i][j]=max(dp[i][j],dp[i-1][j-w[i]*k]+c[i]*k);
        
				}
      
			}
    
		}
  
	}

}

cout<<dp[n][m];

}