#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; }