#include <bits/stdc++.h>
using namespace std;
int l[100005], e[100005], k[100005], dp[100005][2005];
// l = val, e = cost, k = count
int t, n;
int solve(int i, int rem) {
if (i > n or rem <= 0) return 0;
if (dp[i][rem] != -1) return dp[i][rem];
// cout << i << " " << rem << endl;
int res = INT_MIN;
if (rem >= e[i] and k[i] > 0) {
k[i]--;
if (k[i] > 0) {
res = max(res, solve(i, rem-e[i])+l[i]);
}
res = max(res, solve(i+1, rem-e[i])+l[i]);
k[i]++;
}
res = max(res, solve(i+1, rem));
return dp[i][rem] = res;
}
int main() {
cin >> t >> n;
for (int i = 1; i <= n; i++) {
cin >> l[i] >> e[i] >> k[i];
}
memset(dp, -1, sizeof(dp));
cout << solve(1, t) << endl;
// for (int i = 1; i <= n; i++) {
// for (int j = 0; j <= t; j++) {
// cout << dp[i][j] << " ";
// }
// cout << endl;
// }
}
