#include <bits/stdc++.h> using namespace std; typedef long long ll; const ll INF = (ll)(1e18) + 13; int main() { ios::sync_with_stdio(0); cin.tie(0); int s, n; cin >> s >> n; vector<vector<array<int,2>>> W(s+1); int Q[s+1]; for (int i=0; i<n; i++) { int v, w, k; cin >> v >> w >> k; W[w].push_back({v, k}); Q[w] += k; } for (int i=1; i<=s; i++) { if (W[i].size() > 0) { sort(W[i].begin(), W[i].end(), [](auto &a, auto &b) { if (a[0] == b[0]) { return a[1] > b[1]; } return a[0] > b[0]; }); } } vector<ll> dp(s+5, -INF); dp[0] = 0; for (int w=1; w<=s; w++) { if (W[w].size() == 0) continue; int T = s / w; int t = 0; for (auto &item : W[w]) { auto [V, K] = item; for (int i = 0; i < K; i++) { for (int j=s; j>=0; j--) { if (j+w <= s && dp[j] > -INF) { dp[j+w] = max(dp[j+w], dp[j] + V); } } t++; } if (t >= T) break; } } ll ans = 0; for (int i=0; i<=s; i++) { ans = max(ans, dp[i]); } cout << ans << '\n'; }