#include <bits/stdc++.h> #define maxw 2005 using namespace std; vector<pair<int,int>> items[maxw]; vector<pair<int,int>> filtered; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int s,n; cin >> s >> n; for(int i = 0;i < n;i++){ int v,w,k; cin >> v >> w >> k; items[w].push_back({v,k}); } for(int i = 1;i <= s;i++){ if(items[i].empty()) continue; int maxItems = s/i; sort(items[i].rbegin(),items[i].rend()); for(auto item: items[i]){ if(maxItems == 0) break; int change = min(item.second,maxItems); maxItems -= change; for(int j = 0;j < change;j++){ filtered.push_back({item.first,i}); } } } int dp[s+1]{0}; for(auto item: filtered){ for(int i = s;i >= item.second;i--){ dp[i] = max(dp[i],dp[i-item.second] + item.first); } } cout << dp[s]; return 0; }