#include<bits/stdc++.h>
using namespace std;
long long m,n,ans;
long long v[100000], w[100000];
long long dp[100000],sum=0;
int main(){
	scanf("%d%d",&m, &n);
   	for (long long i=1; i<=n; i++)
    {
   		long long vv,ww,nn;
   		cin>>vv>>ww>>nn;
   		if(nn<0)
		{
   		 	nn=1;
		}
		else if(nn==0)
		{
			nn=m/vv;
		}
		for(int k=1;k<=nn;k*=2){
			v[++sum]=vv*k;
			w[sum]=ww*k;
			nn-=k;
		}
		if(nn>0){
			v[++sum]=nn*vv;
			w[sum]=nn*ww;
		}
	}
	for(int i=1;i<=sum;i++){
		for(int j=m;j>=v[i];j--){
			dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
		}
	}
	cout<<dp[m];
	return 0;
}