#include<bits/stdc++.h>
using namespace std;
long long int n,m,v[1001],w[1001],dp[1001],sum=0;
int main(){
	cin>>m>>n;
	for(int i=1;i<=n;i++){
		int vv,ww,nn;
		cin>>vv>>ww>>nn;
		if(nn==1){
			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-v[i]]+w[i],dp[j]);
		}
	}
	cout<<dp[m];
	return 0;
}