#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;
}
