#include <bits/stdc++.h> using namespace std; #define int long long #define endl '\n' #define ff first #define ss second #define m_p make_pair #define INF LLONG_MAX using vi=vector<int>; using vvi=vector<vi>; using pii=pair<int,int>; using vpii=vector<pii>; int32_t main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); int s,n; cin>>s>>n; vector<vpii> v(s+1); while(n--){ int value,w,k; cin>>value>>w>>k; v[w].push_back({value,k}); } vvi pref(s+1,vi(s+1,-1)); for(auto i=0;i<=s;i++) { vpii c=v[i]; if(c.empty()) continue; sort(c.begin(),c.end(),greater<pii>()); int it=0; int sum=c[0].ss; int ant=0; while(sum<=s){ for(int j=ant;j<sum;j++) pref[i][j]=it; if(it==c.size()-1) break; it++; ant=sum; sum+=c[it].ss; } } vi dp(s+1,-1); dp[0]=0; vector<pair<pair<int,int>,vi> > f(s+1,{{-1,-1},vi(s+1,0)}); f[0].ff={0,0}; for(int i=0;i<=s;i++){ if(dp[i]==-1) continue; f[i].ss[f[i].ff.ss]=1; for(int j=0;j<=s-i;j++){ if(v[j].empty()) continue; f[i].ss[j]+=f[f[i].ff.ff].ss[j]; int it=pref[j][f[i].ss[j]]; if(it==-1) continue; int s=i+j; if(dp[s]<dp[i]+v[j][it].ff){ dp[s]=dp[i]+v[j][it].ff; f[s].ff={i,j}; } } } int ans=0; for(auto i : dp) ans=max(ans,i); cout<<ans<<endl; return 0; }