#include <bits/stdc++.h>

#define N 4004

#define setIO(s) freopen(s".in","r",stdin)

using namespace std;

int f[N];

struct P

{

    int t,f,h;

    P(int t=0,int f=0,int h=0):t(t),f(f),h(h){}

}t[N];

bool cmp(P a,P b)

{

    return a.t<b.t;

}

int main()

{

    int D,n,i,j,mx=0;

    // setIO("input");

    scanf("%d%d",&D,&n);

    for(i=1;i<=n;++i) scanf("%d%d%d",&t[i].t,&t[i].f,&t[i].h);

    sort(t+1,t+1+n,cmp);

    f[0]=10;

    for(i=1;i<=n;++i)

    {

        for(j=D;j>=0;--j)

        {

            if(f[j]>=t[i].t)

            {

                if(j+t[i].h>=D)

                {

                    printf("%d\n",t[i].t);

                    return 0;

                }

                f[j+t[i].h]=max(f[j+t[i].h], f[j]);

                f[j]+=t[i].f;

                mx=max(mx, f[j]);

            }

        }

    }

    printf("%d\n",mx);

    return 0;

}