#include <bits/stdc++.h> using namespace std; using ll = long long; int s, n; vector<pair<int,int>> W[2005]; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); cin >> s >> n; for(int i = 1; i <= n; i++){ int v, w, k; cin >> v >> w >> k; if(w <= s && k > 0) W[w].push_back({v, k}); } vector<ll> dp(s+1, 0); // duyệt theo trọng lượng for(int w = 1; w <= s; w++){ if(W[w].empty()) continue; // lấy các value, tối đa S / w món vector<int> vals; for(auto &[v, k] : W[w]){ int take = min(k, s / w); while(take--) vals.push_back(v); } if(vals.empty()) continue; sort(vals.begin(), vals.end(), greater<int>()); int m = vals.size(); vector<ll> pre(m+1, 0); for(int i = 0; i < m; i++) pre[i+1] = pre[i] + vals[i]; vector<ll> new_dp = dp; // group knapsack for(int t = 1; t <= m; t++){ int weight = t * w; if(weight > s) break; for(int x = weight; x <= s; x++){ new_dp[x] = max(new_dp[x], dp[x - weight] + pre[t]); } } dp.swap(new_dp); } cout << *max_element(dp.begin(), dp.end()); return 0; }