#include <bits/stdc++.h> #define ll long long #define db long double #define pll pair<ll,ll> #define foru(i,a,b) for(int i=(a);i<=(b);i++) #define ford(i,a,b) for(int i=(a);i>=(b);i--) #define ALL(a) (a).begin(),(a).end() #define ROUND(i) fixed<<setprecision(i) #define fi first #define se second using namespace std; ll n,S; vector<pll>a[2003]; vector<ll>f[2003]; ll dp[2003]; signed main(){ ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin>>S>>n; foru(i,1,n){ ll w,v,k;cin>>v>>w>>k; a[w].push_back({v,k}); } foru(w,1,S){ sort(ALL(a[w]),greater<pll>()); ll dem=(S/w); f[w].assign(dem+2,0); ll i=0; for(auto [v,k]:a[w]){ while(dem>0&&k>0){ k--;dem--; f[w][++i]=v; } } } ll res=0; foru(i,1,S){ foru(t,1,f[i].size()-1){ if(f[i][t]>0){ ford(j,S,i){ dp[j]=max(dp[j],dp[j-i]+f[i][t]); res=max(res,dp[j]); } } } } cout<<res; return 0; }