#include<bits/stdc++.h>
using namespace std;
#define MAX 1001
int weight,n;			//背包容量 物品种数
int w[MAX],v[MAX],p[MAX];		//w重量，v价值，p最多件数
int dp[MAX][MAX];
int f(int n,int weight){
	if(n==1){			//物品剩最后一种
		if(weight>=w[1])
			if(p[1]>weight/w[1]) return v[1]*(weight/w[1]);
			else return v[1]*p[1];
		else return 0;
	}
	if(dp[n][weight]>0) return dp[n][weight];
	if(weight<w[n]) dp[n][weight]=f(n-1, weight);
		else{
			dp[n][weight] =f(n-1,weight);
			for(int i=1;i<=p[n]&&i*w[n]<=weight;i++)
				dp[n][weight]=max(dp[n][weight],f(n-1,weight-i*w[n])+v[n]*i);
		}
	return dp[n][weight];
}
		
int main(){
	scanf("%d%d",&weight,&n);
	for(int i=1;i<=n;i++){
		scanf("%d%d%d",&w[i],&v[i],&p[i]);
		if(p[i]==0)p[i]=weight/w[i];			//把完全背包转换成多重背包，p这时候是最大的件数
	}
	memset(dp,0,sizeof(dp));
	printf("%d",f(n,weight));
	return 0;
}