#include <bits/stdc++.h>
#define int long long
#define ii pair<int,int>
#define iii pair<int,ii>
#define ff first
#define ss second
using namespace std;
const int maxn=1e6+5,inf=1e18;
int n,m,nn,k,p,q;
int b[maxn],a[maxn],c[maxn],ans;
int dp[maxn];
vector<ii> val[2005];
void solve()
{
cin>>m>>nn;
for (int i=1,x,y,z;i<=nn;i++)
{
cin>>x>>y>>z;
val[y].push_back({x,z});
}
for (int i=1;i<=m;i++)
{
sort(val[i].begin(),val[i].end(),greater<ii>());
int sp=(m/i);
for (auto [x,y]:val[i])
{
int cur=min(sp,y);
sp-=cur;
for (int k=1;k<=cur;k++) a[++n]=x,b[n]=i;
if (!sp) break;
}
}
ans=0;
for (int i=1;i<=n;i++)
for (int j=m;j>=b[i];j--)
{
dp[j]=max(dp[j],dp[j-b[i]]+a[i]);
ans=max(ans,dp[j]);
}
cout<<ans;
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
solve();
}
