#include<bits/stdc++.h>
using namespace std;
struct item { int v,w,k; };
bool sortt(item a,item b) { if(a.w==b.w) return a.v>b.v;return a.w<b.w; }
const int MAXN=2024;
const long long INF=1e18;
vector<int> vi[MAXN];
long long dp[MAXN];
item A[MAXN*50];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int s,n;
cin>>s>>n;
for(int i=1;i<=n;i++) cin>>A[i].v>>A[i].w>>A[i].k;
sort(A+1,A+n+1,sortt);
for(int i=1;i<=n;i++)
{
if(A[i].w>s) break;
while(A[i].k--&&(int)vi[A[i].w].size()*A[i].w<=s) vi[A[i].w].push_back(A[i].v);
}
for(int i=1;i<=s;i++) dp[i]=-INF;
for(int i=1;i<=s;i++)
{
for(int j=s;j>=0;j--)
{
int p=j;
long long w=0;
for(auto v:vi[i])
{
if((p+=i)>s) break;
w+=v,dp[p]=max(dp[p],dp[j]+w);
}
}
}
long long ans=0;
for(int i=0;i<=s;i++) ans=max(ans,dp[i]);
cout<<ans;
}
