#include <bits/stdc++.h>
using namespace std;
int s,n;
int w[100005];
long long v[100005],k[100005],dp[2005];
priority_queue<pair<long long,long long>> q[2005];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cin>>s>>n;
for(int i=0;i<n;i++)
{
cin>>v[i]>>w[i]>>k[i];
q[w[i]].push({v[i],k[i]});
}
for(int x=1;x<=s;x++)
{
long long c=s/x;
while(!q[x].empty() && c>0)
{
pair<long long,long long> p=q[x].top();
q[x].pop();
long long t=p.second;
if(t>c)
{
t=c;
}
c-=t;
for(int y=0;y<t;y++)
{
for(int z=s;z>=x;z--)
{
dp[z]=max(dp[z],dp[z-x]+p.first);
}
}
}
}
long long a=0;
for(int i=1;i<=s;i++)
{
a=max(a,dp[i]);
}
cout<<a;
return 0;
}
