#include <stdio.h>
#include <stdlib.h>
#define maxn 10000
int f[maxn];
int w[maxn][maxn];
int v[maxn][maxn];
int max(int a,int b)
{
    return a>b?a:b;
}
int cc[maxn]
int main()
{
    int m,n;
    scanf("%d %d",&m,&n);
    int a,b,c;
    int i,j,k;
    int num=0;
    while(scanf("%d %d %d",&a,&b,&c)!=EOF){
        num=max(c,num);///num记录组数
        cc[c]++;
        w[c][cc[c]]=a;
        v[c][cc[c]]=b;
    }
    
    for(k=1;k<=num;k++){
        for(j=m;j>=1;j--){
                for(i=1;i<=cc[k];i++){
                if(j>=w[k][i]){
                    f[j]=max(f[j],f[j-w[k][i]]+v[k][i]);
                }

            }
        }
    }

    printf("%d",f[m]);
    return 0;
}