#include <bits/stdc++.h>
using namespace std;
int obj[100000][3] ;
pair<int,int> dp[100001][2001];
pair<int,int> max(pair<int,int> a, pair<int,int> b) {
if (a.first > b.first) return a;
if (b.first > a.first) return b;
if (a.second < b.second) return a;
return b;
}
int main() {
int s, n; cin >> s >> n;
//vector<array<int,3>> obj(n);
for (int i = 0; i < n; i++) cin >> obj[i][0] >> obj[i][1] >> obj[i][2];
//vector<vector<pair<int,int>>> dp(n,vector<pair<int,int>>(s+1));
//for (int i = 0; i < n+1; i++) dp[0][i] = 0;
/*for (int i = 0; i < s+1; i++) {
for (int j = 0; j < n; j++) {
if (i-obj[j][1] >= 0) {
if (dp[i-obj[j][1]][j+1] < obj[j][2]) {
if (dp[i][0] < dp[i-obj[j][1]][0]+obj[j][0]) {
dp[i] = dp[i-obj[j][1]];
dp[i][0] += obj[j][0];
dp[i][j+1]++;
}
else if (dp[i][0] == dp[i-obj[j][1]][0]+obj[j][0] && dp[i-obj[j][1]][j+1]+1<dp[i][j+1]) {
dp[i] = dp[i-obj[j][1]];
dp[i][0] += obj[j][0];
dp[i][j+1]++;
}
}
}
}
}*/
for (int i = 0; i < n; i++) for (int j = 0; j <= s; j++) dp[i][j] = make_pair(0,0);
for (int i = 0; i < n; i++) {
for (int j = 1; j <= s; j++) {
if (j-obj[i][1] >= 0) {
for (int k = 1; j-obj[i][1]*k>=0; k++) if (i > 0 && k <= obj[i][2]) dp[i][j] = max(dp[i][j],make_pair(dp[i-1][j-obj[i][1]*k].first+obj[i][0]*k,k));
if (dp[i][j-obj[i][1]].second < obj[i][2]) dp[i][j] = max(dp[i][j],make_pair(dp[i][j-obj[i][1]].first+obj[i][0],dp[i][j-obj[i][1]].second+1));
}
if (i > 0) dp[i][j]= max(dp[i][j],make_pair(dp[i-1][j].first,0));
}
}
int ans = 0;
for (int j = 0; j < n; j++) for (int i = 0; i <= s; i++) ans = max(dp[j][i].first,ans);
cout << ans << endl;
}
