#include <bits/stdc++.h> using namespace std; #define ll long long #define ld long double #define ull unsigned long long #define pll pair<ll, ll> #define ppll pair< pair<long long, long long>, long long > #define ff first #define ss second #define pb push_back #define pf push_front const ll DIM = 1e6 + 7; const ll INF = 1e18; const ll mod = 1e9 + 7; const ll maxlog = 20; const ll bsize = 350; ll dp[107][2007]; map<ll, vector<pll> > m; void solve() { ll s, n; cin >> s >> n; for (int i=1; i<=n; i++) { ll val, w, k; cin >> val >> w >> k; m[val].pb({w, k}); } ll k = 0; for (auto [val, v] : m) { ++k; sort(v.begin(), v.end()); for (int nw = 0; nw <= s; nw++) { dp[k][nw] = dp[k-1][nw]; ll sumw = 0, i = 0, cur = 0; for (int p=1; p<=s; p++) { if (v[i].ss == cur) { i++; cur = 0; if (i == v.size()) break; } cur++; sumw += v[i].ff; if (sumw > nw) break; dp[k][nw] = max(dp[k][nw], dp[k-1][nw - sumw] + p*val); } } } ll ans = 0; for (int i=s; i>=0; i--) { ans = max(ans, dp[k][i]); } cout << ans << endl; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int ntest = 1; //cin >> ntest; while (ntest--) { solve(); } return 0; } ;