#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define fi first
#define se second
using namespace std;
const int N = 1e5 + 7;
const int M = 2e3 + 7;
int dp[M], cnt[N];
pii item[N][33];
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int s, n; cin >> s >> n;
for (int i = 1; i <= n; i++) {
int v, w, k; cin >> v >> w >> k;
for (int j = 1; j <= k; j++) {
cnt[w]++;
item[w][cnt[w]] = {v, 1};
}
}
for (int w = 1; w <= s; w++) {
if (cnt[w] == 0) continue;
sort(item[w] + 1, item[w] + cnt[w] + 1, [&](pii a, pii b){
return a.first > b.first;
});
int sum = 0;
for (int i = 1; i <= cnt[w]; i++) {
int v = item[w][i].first;
for (int j = s; j >= w; j--) dp[j] = max(dp[j], dp[j - w] + v);
sum += w;
if (sum > s) break;
}
}
cout << dp[s] << '\n';
return 0;
}
