//#pragma GCC optimize("O3") //#pragma GCC optimize("unroll-loops") //#pragma GCC target("avx,avx2") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2") //#pragma GCC optimize("trapv") #include <bits/stdc++.h> using namespace std; #define fi first #define se second #define pb push_back #define all(x) x.begin(), x.end() #define mpr make_pair typedef long long ll; typedef unsigned long long ull; typedef long double ld; const int nmax = 5011, mod = 1000000007, inf = 2000010000, key = 200003, lg = 20, block = 300; const ll infll = 4000000000000000000; const ld eps = 1e-9; int dp[nmax]; vector<array<int, 2>> all_items[nmax]; void solve() { int capacity, n, value, weight, amount; cin >> capacity >> n; for(int i = 0; i < n; i++) { cin >> value >> weight >> amount; all_items[weight].pb({value, amount}); } vector<array<int, 2>> useful_items; for(int i = 1; i <= capacity; i++) { int max_amount = capacity / i; int cur_amount = 0; sort(all(all_items[i])); reverse(all(all_items[i])); for(auto j : all_items[i]) { int rem = max_amount - cur_amount; rem = min(rem, j[1]); cur_amount += rem; for(int k = 0; k < rem; k++) useful_items.pb({i, j[0]}); if(cur_amount == max_amount) break; } } for(auto item : useful_items) { for(int cur_capacity = capacity; cur_capacity >= item[0]; cur_capacity--) dp[cur_capacity] = max(dp[cur_capacity], dp[cur_capacity - item[0]] + item[1]); } cout << dp[capacity] << "\n"; return ; } int main() { //freopen("spainting.in","r",stdin); //freopen("spainting.out","w",stdout); ios_base::sync_with_stdio(0);cin.tie(0); srand(8713); //init(); int t = 1; //cin >> t; //int t_ = t; //t = rdi(); while(t--) { //cout << "Case #" << t_ - t << ": "; solve(); } //flush(); return 0; } /* */