#include <iostream>
#include <cmath>
#include <cstring>
#include <string.h>
#include <queue>
#include <stack>
#include <map>
using namespace std;
const int N = 1e5 + 10;
const int INF = 0x3f3f3f3f;
int w[N],v[N],dp[N],n,m,len ,ww,vv,num;
int main(){
	cin >> m >> n;
	for(int i=1; i<=n ;i++)
	{
		cin >> ww >> vv >> num;
		int cnt = 1;
		while(cnt <= num){
			w[++len]=cnt*ww;
			v[len]=cnt*vv;
			num -= cnt;
			cnt <<= 1;
		}
		if(num > 0){
			w[++len]=num*ww;
			v[len]=num*vv;
		}
		
	}
	n = len;
	for(int i=1; i<=n; i++)
	{
		for(int j=m; j>=w[i]; j--){
			dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
		}
	}
	cout << dp[m];
	return 0;
}//二进制解法