unsigned rng=12345; int rand_(){return (rng*=3)>>1;}
int(*compar)(int,int);
void sort_(int*a,int l,int r)
{
while(l<r)
{
int i=l,j=l,k=r,t,p=a[l+rand_()%(r-l)];
while(j<k)
switch(compar(a[j],p))
{
case 0:++j;break;
case -1:t=a[i],a[i]=a[j],a[j]=t,++i,++j;break;
case 1:t=a[--k],a[k]=a[j],a[j]=t;break;
}
sort_(a,l,i);
l=k;
}
}
int min_(int a,int b){return a<b?a:b;}
long long max_(long long a,long long b){return a>b?a:b;}
#include<stdio.h>
#include<stdlib.h>
#define S 2005
#define N 100005
int s,n,v[N],w[N],k[N];
int *eh[N],eo[N];
void append(int i,int j)
{
int o=eo[i]++;
if(o>=2&&(o&o-1)==0)eh[i]=(int*)realloc(eh[i],2*o*sizeof**eh);
eh[i][o]=j;
}
int c0(int i,int j){return v[i]<v[j]?1:v[i]>v[j]?-1:0;}
#define SlgS (S*13)
int vv[SlgS],ww[SlgS],oo;
long long dp[S];
int main()
{
scanf("%d%d",&s,&n);
for(int i=1;i<=s;++i)eh[i]=(int*)realloc(0,sizeof**eh*2);
for(int i=1;i<=n;++i)
scanf("%d%d%d",v+i,w+i,k+i),
append(w[i],i);
compar=c0;
for(int i=1;i<=s;++i) sort_(eh[i],0,eo[i]);
for(int i=1;i<=s;++i)
{
int left=(s+i-1)/i;
for(int j=0;left&&j<eo[i];++j)
{
int take=min_(left,k[eh[i][j]]);
for(int k=0;k<take;++k)
{
vv[oo]=v[eh[i][j]];
ww[oo]=w[eh[i][j]];
++oo;
}
left-=take;
}
dp[i]=-1e18;
}
for(int i=0;i<oo;++i)
{
for(int j=s;j>=ww[i];--j)
{
dp[j]=max_(dp[j],dp[j-ww[i]]+vv[i]);
dp[s+1]=max_(dp[s+1],dp[j]);
}
}
printf("%lld",dp[s+1]);
}
