#include <bits/stdc++.h>
using namespace std;
#define int long long
struct seg {
int v , w , k;
};
signed main() {
ios::sync_with_stdio(0); cin.tie(NULL);
cout.tie(NULL);
int s , n; cin >> s >> n;
vector<seg> a(n + 1);
for (int i = 1 ; i <= n ; i++) {
cin >> a[i].v >> a[i].w >> a[i].k;
}
vector<vector<int>> f;
vector<int> g;
f.assign(n + 1 , vector<int> (s + 1 , 0));
for (int i = 1 ; i <= n ; i++) {
g.assign(s + 1 , 0);
for (int j = 0 ; j <= s ; j++) {
if (a[i].w <= j) {
if ((f[i][j - a[i].w] + a[i].v) > f[i - 1][j] && (g[j - a[i].w] + 1) <= a[i].k) {
f[i][j] = f[i][j - a[i].w] + a[i].v;
g[j] = g[j - a[i].w] + 1;
}
else f[i][j] = max(f[i][j] , f[i - 1][j]);
}
else f[i][j] = f[i - 1][j];
}
}
int ans = 0;
for (int i = 0 ; i <= s ; i++) {
ans = max(ans , f[n][i]);
}
cout << ans;
return 0;
}
