#include <bits/stdc++.h>
#define eggy using
#define party namespace 
eggy party std;
int n,m,t,i,j,k,I,J,K,l,r;
struct wp
{
    int v,w,t;
};
struct wp p[32];
int z[12],a[202],cnt = 1;
inline int read();bool cmp(struct wp a,struct wp b);
int main()
{
    m = read(); n = read();
    for (i = 1; i <= n; i++)
    {
        p[i].v = read();p[i].w = read();p[i].t = read();
        t = max(t,p[i].t);
        if (p[i].t != p[i-1].t) z[cnt++] = i;
    }z[cnt] = n+1;
    sort(p + 1, p + n + 1, cmp);
    for (i = 1; i <= t; i++)
    {
        for (k = m; k > 1; k--)
        {
            for (j = z[i]; j < z[i+1]; j++) 
            {
                if (k - p[i].v >= 0)
                    a[k] = max(a[k],a[k - p[j].v] + p[j].w);
            }            
        }
    }
    printf("%d",a[m]);
    return 0;
}
inline int read()
{
    char a = 0;
    int b = 0,c = 1;
    while (a < '0' || a > '9')
    {
        a = getchar();
        if (a == '-') c = -1;
    }
    while (a >= '0' && a <= '9')
    {
        b = (b << 3) + (b << 1) + a - 48;
        a = getchar();
    }
    return b * c;
}
bool cmp(struct wp a,struct wp b)
{
    return a.t < b.t;
}