#include<bits/stdc++.h> using namespace std; int main() { int s , n; cin >> s >> n; vector<vector<pair<int,int>>> weight_to_info(s + 1); for(int i = 0;i < n; i++){ int v , w , k; cin >> v >> w >> k; weight_to_info[w].push_back({v , k}); } vector<pair<int,int>> cantake; for(int i = 1;i <= s; i++){ sort(weight_to_info[i].begin(), weight_to_info[i].end()); int cur = 0; for(auto &x : weight_to_info[i]){ while(cur < s && x.second > 0){ cur++; cantake.push_back({x.first, i}); x.second--; } } } //knapsack: vector<vector<int>> dp(cantake.size() + 1 , vector<int> (s + 1, 0)); dp[0][0] = 0; for(int i = 1;i <= cantake.size() ;i++) { for(int j = 0;j <= s; j++) { dp[i][j] = dp[i - 1][j]; int w = cantake[i - 1].second; int cost = cantake[i - 1].first; if( j - w >= 0){ dp[i][j] =max(dp[i][j] , dp[i - 1][j - w] + cost); } } } cout << dp[cantake.size()][s] << endl; }