#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> pii; // const const ll LINF = (ll)(1e18) + 5; const int INF = (int)(1e9) + 5; // loop #define FOR(i, l, r) for (int i=l; i<r; i++) #define F0R(i, n) for (int i=0; i<n; i++) int main() { ios::sync_with_stdio(0); cin.tie(0); int S, N; cin >> S >> N; vector<vector<pii>> W(S+1); for (int i=0; i<N; i++) { int v, w, k; cin >> v >> w >> k; W[w].push_back({v, k}); } for (int i=1; i<=S; i++) { if (W[i].size() > 0) { sort(W[i].rbegin(), W[i].rend()); } } vector<int> dp(S+1, -INF); dp[0] = 0; for (int w = 1; w <= S; w++) { if (W[w].size() == 0) continue; int maxt = S / w; int cnt = 0; for (auto &[v, k] : W[w]) { for (int i = 0; i < k && cnt < maxt; i++) { for (int x=S-w; x>=0; x--) { if (dp[x] > -INF) { dp[x + w] = max(dp[x + w], dp[x] + v); cnt++; } } } if (cnt >= maxt) { break; } } } int ans = 0; for (int i=0; i<=S; i++) { ans = max(ans, dp[i]); } cout << ans << '\n'; }