#include <stdio.h>
long long max(long long m,long long n)
{
    if(m>n) return m;
    else    return n;
}
int main()
{
    int m,n;//总重量，物体个数
    scanf("%d%d",&m,&n); 
    long long f[1005];
    int i,j,k=0,x;
    int a[n+1],b[n+1],c[n+1];//重量，价值，组别
    for(i=1;i<=n;i++)
    {
        scanf("%d%d%d",&a[i],&b[i],&c[i]);
        k=max(k,c[i]);
    }
    for(i=1;i<=k;i++)
        for(j=m;j>=0;j--)
            for(x=1;x<=n;x++)
            {
                if(c[x]!=i||j<a[x]) continue;
                f[j]=max(f[j],f[j-a[x]]+b[x]);
            }
    printf("%lld",f[m]);
    return 0;
}