#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int S = 2010;
const int N = 1e5 + 10;
int cnt[S];
int v[N], w[N], k[N];
int dp[S];
int main (int argc, char const *argv[]) {
ios_base::sync_with_stdio(0);
cin.tie(0);
int s, n; cin >> s >> n;
for(int i = 1; i <= n; ++i) cin >> v[i] >> w[i] >> k[i];
vector<int> perm(n);
iota(perm.begin(), perm.end(), 1);
sort(perm.begin(), perm.end(), [](int x, int y) {
return v[x] > v[y];
});
for(int i : perm) {
for(int c = 0; c < k[i]; ++c) {
if(cnt[w[i]] * w[i] > s) break;
for(int j = s; j >= w[i]; --j) {
dp[j] = max(dp[j], dp[j-w[i]] + v[i]);
}
++cnt[w[i]];
}
}
cout << dp[s];
return 0;
}
