#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
using ll=long long;
const int N=1e5;
const int M=2e6;
int s,n,n1=0;
struct node{
int v;
int w;
int k;
}a[N+5],b[M+5];
int dp[2005];
vector<pair<int,int>>g[2005];
int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>s>>n;
for(int i=1;i<=n;++i){
cin>>a[i].v>>a[i].w>>a[i].k;
g[a[i].w].push_back({a[i].v,a[i].k});
}
for(int i=1;i<=s;++i){
sort(g[i].begin(),g[i].end(),greater<pair<int,int>>());
int cur=0;
for(int j=0;j<(int)g[i].size();++j){
while(cur<s/i&&g[i][j].se>0){
g[i][j].se--;
cur++;
for(int l=s-i;l>=0;--l)
dp[l+i]=max(dp[l+i],dp[l]+g[i][j].fi);
}
}
}
int ans=0;
for(int i=0;i<=s;++i)
ans=max(ans,dp[i]);
cout<<ans;
return 0;
}
