#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
using namespace std;
signed main (){
int s,n; cin >> s >> n;
pair<int,int> dp[n+1][s+1];
int w[n+1],h[n+1],k[n+1];
memset(dp,0,sizeof dp);
for(int i =1;i<=n;i++){
cin >> h[i] >> w[i] >> k[i];
}
for(int i = 1;i<=n;i++){
for(int j = 1;j<=s;j++){
int tmp = 0,con = 0;
if(j - w[i] >= 0){
tmp = dp[i][j-w[i]].fi + h[i];
con = dp[i][j-w[i]].se + 1;
}
dp[i][j].fi = max(dp[i][j-1].fi,dp[i-1][j].fi);
if(dp[i][j].fi == dp[i][j-1].fi) dp[i][j].se = dp[i][j-1].se;
else dp[i][j].se = 0;
if(con <= k[i]){
if(max(dp[i][j].fi,tmp) == tmp){
dp[i][j].fi = tmp;
dp[i][j].se = con;
}
} else{
dp[i][j].fi += dp[i-1][j - k[i]*w[i]].fi;
}
// cout << dp[i][j].fi << " ";
}
// cout << endl;
}
cout << dp[n][s].fi << endl;
return 0;
}
