#include <bits/stdc++.h>
using namespace std;
#define all(v) v.begin(),v.end()
#define eb emplace_back
#define ll long long
#define fi first
#define se second
int t,n,i,u,v,w,m;
map<int,vector<pair<int,int>>> mp;
const int maxn = 1e4 + 10;
const ll inf = 1e16;
ll dp[maxn],mx;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cin>>n>>m;
while(m--)
{
cin>>u>>v>>w;
mp[v].eb(make_pair(u,w));
// cout<<u<<' '<<v<<'\n';
}
dp[0] = 0;
for(i = 1;i<=n;i++)dp[i] = -inf;
for(auto [w,a] : mp)
{
sort(all(a),greater<>());
for(i = n;i;i--)
{
int c = 0,id = 0,cc = 0;
ll v = 0;
while(i >= c * w)
{
if(dp[i - c * w] != INT_MIN)dp[i] = max(dp[i],dp[i - c * w] + v);
c++;
cc++;
if(id >= a.size())break;
v += a[id].fi;
if(cc == a[id].se)
{
id++;
cc = 0;
// cout<<w<<'\n';
}
}
mx = max(mx,dp[i]);
}
}
// for(i = 0;i<=n;i++)cout<<dp[i]<<'\n';
cout<<mx;
return 0;
}
