#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;

struct bag{
	int a,b,c;
}p[N];

int dp[N];
int m,n;
bool cmp(bag a,bag b){
	return a.c <= b.c;
}

int main(){
    cin>>m>>n;
    for(int i = 1;i <= n;++i) cin>>p[i].a>>p[i].b>>p[i].c;
    
    sort(p+1,p+n+1,cmp);
    
    for(int start = 1,end = 2;start <= n;){
        while(end <= n && p[start].c == p[end].c) end++;
        for(int i = m;i >= 0;--i){
            for(int j = start;j < end;++j){
                if(i >= p[j].a)
                    dp[i] = max(dp[i],dp[i-p[j].a] + p[j].b);
            }
        }
        start = end;
    }
    cout<<dp[m];
    return 0;
}