///TRAN THAI BAO :3 #include <iostream> #include <cstdio> #include <vector> #include <algorithm> using namespace std; #define maxS 2007 #define maxN 30007 typedef pair<long long, long long> pii; int n; long long S; vector<pii>itm[maxS]; vector<pii>realItm; long long dp[maxN][maxS] = {0}; bool cmp(pii x, pii y) { return x.first > y.first; } void readData() { realItm.push_back({0, 0}); cin >> S >> n; long long v, w, a; for(int i = 1; i <= n; i++) { cin >> v >> w >> a; itm[w].push_back({v, a}); } for(int i = 1; i <= S; i++) { sort(itm[i].begin(), itm[i].end(), cmp); int lim = S/i, cnt = 0; for(int j = 0; j < itm[i].size(); j++) { if(cnt >= lim)break; for(int k = 0; k < itm[i][j].second; k++) { realItm.push_back({itm[i][j].first, i}); cnt++; if(cnt >= lim)break; } } } n = realItm.size()-1; } void knapSack() { for(int i = 1; i <= n; i++) { pii cur = realItm[i]; for(int j = 0; j <= S; j++) { dp[i][j] = max(dp[i][j], dp[i-1][j]); if(cur.second <= j) dp[i][j] = max(dp[i][j], dp[i-1][j-cur.second]+cur.first); } } cout << dp[n][S]; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); readData(); knapSack(); return 0; }