#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define val 2*1e3+1
signed main() {
ll w, n; cin>>w>>n; vector<ll> y(n+1), v(n+1), k(n+1), dp(w+1, 0);
vector<vector<pair<ll, ll>>> a(w+1);
vector<vector<ll>> b(w+1, vector<ll>(val, 0));
for(ll i=0; i<n; i++)
{
cin>>v[i]>>y[i]>>k[i]; a[y[i]].push_back({v[i], min(k[i], w/y[i])});
}
for(ll i=1; i<=w; i++)
{
sort(a[i].rbegin(), a[i].rend());
b[i].assign((w/i)+1, 0); ll t=0;
for(auto x: a[i])
{
for(ll j=0; j<min(x.second, (w/i)-t); j++)
{
t++; b[i][t]=b[i][t-1]+x.first;
}
if(t==(w/i))break;
}
for(ll j=t+1; j<=(w/i); j++)b[i][j]=b[i][t];
}
for(ll i=0; i<=w; i++)
{
if(b[i].empty())continue; vector<ll> nd=dp;
for(ll j=0; j<=w; j++)
{
for(ll o=1; o<(b[i].size())&&j+o*i<=w; o++)
{
nd[j+o*i]=max(nd[j+o*i], dp[j]+b[i][o]);
}
}
dp=nd;
}
cout<<dp[w]<<endl;
}
