#include <bits/stdc++.h> // solved by bekagg #define int long long #define ent '\n' #define pb push_back #define all(x) x.begin(),x.end() #define PRaim_bek_abi ios_base::sync_with_stdio(0);cin.tie(0); using namespace std; const int N = 1e5+5; const int MOD = 1e9+7; int n , s , v[N] , w[N] , k[N]; int dp[N]; void arkanefury228(){ cin >> s >> n; vector<pair<int , pair<int , int> > > g; for (int i = 1; i <= n; i++){ cin >> v[i] >> w[i] >> k[i]; k[i] = min(k[i] , s); g.pb({v[i] , {w[i] , k[i]}}); } sort(all(g)); reverse(all(g)); for (int i = 1; i <= n; i++){ v[i] = g[i - 1].first; w[i] = g[i - 1].second.first; k[i] = g[i - 1].second.second; for (int j = s; j >= w[i]; j--){ if (dp[j - w[i]] + v[i] >= dp[j]){ for (int cnt = 1; cnt <= k[i]; cnt++){ if (j + (cnt - 1) * w[i] > s) break; dp[j + (cnt - 1) * w[i]] = max(dp[j + (cnt - 1) * w[i]] , dp[j - w[i]] + v[i] * cnt); } } } } int ans = 0; for (int i = 1; i <= s; i++) ans = max(ans , dp[i]); cout << ans; } signed main(){ PRaim_bek_abi int t=1; //cin>>t; for (int respagold = 1; respagold <= t; respagold++) arkanefury228(); }