#include <bits/stdc++.h> using namespace std; #define int long long int32_t main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int n, s; cin >> s >> n; vector<int> v(n), w(n), k(n), dp(s + 1); for (int i = 0; i < n; i++) cin >> v[i] >> w[i] >> k[i]; vector<vector<pair<int, int>>> W(s + 1); for (int i = 0; i < n; i++) { if (w[i] <= s) W[w[i]].emplace_back(v[i], k[i]); } for (int i = 0; i <= s; i++) sort(W[i].rbegin(), W[i].rend()); for (int i = 1; i <= s; i++) { auto ndp = dp; for (int j = 1; j <= s; j++) { int cw = 0, jj = j; for (auto [x, y] : W[i]) { int yy = y; // if (j == s) cout << x << ' ' << y << '\n'; for (;;) { // if (j == s) cout << "jj: " << jj << " yy: " << yy << " cw: " << cw << '\n'; if (jj - i >= 0 && yy - 1 >= 0) jj -= i, yy--, cw += x, ndp[j] = max(ndp[j], dp[jj] + cw); else break; } } } dp = ndp; // for (int i : dp) cout << i << ' '; // cout << '\n'; } cout << *max_element(dp.begin(), dp.end()) << '\n'; return 0; }