#include <bits/stdc++.h>
using namespace std;
#define en '\n'
#define sp ' '
typedef long long ll;
#define Linux ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pii pair<int,int>
const int N=2e3+5;
const int M=1e9+7;
int s,n;
vector<pii> v[N];
int cnt[N][N];
ll dp[N];
int val,wei,k;
ll mx;
int idx;
int main(){Linux
cin >> s >> n;
for(int i=1;i<=n;i++){
cin >> val >> wei >> k;
v[wei].push_back({val,k});
}
for(int i=1;i<=s;i++){
sort(v[i].begin(),v[i].end(),greater<pii>());
for(int j=0;j<v[i].size();j++){
swap(v[i][j].first,v[i][j].second);
if(j>0){
v[i][j].first+=v[i][j-1].first;
}
}
}
// for(int i=1;i<=s;i++){
// cout << i << (i<10?" : ":": ");
// for(auto [count,vv]:v[i]){
// cout << count << ',' << vv << sp;
// }
// cout << en;
// }
for(int i=1;i<=s;i++){
// cout << i << (i<10?" : ":": ");
mx=0;
idx=0;
for(int j=1;j<=i;j++){
if(v[j].empty())continue;
if(cnt[i-j][j]==v[j].back().first)continue;
auto it=upper_bound(v[j].begin(),v[j].end(),make_pair(cnt[i-j][j],M))-v[j].begin();
if(it>=v[j].size()){
// cout << j << "out ";
continue;
}
// cout << "cntbef" << cnt[i-j][j] << 'j' ;
// cout << j << ',' << it << "value" << v[j][it].second << sp;
// cout << v[j][it].first << sp;
if(mx<v[j][it].second+dp[i-j]){
mx=v[j][it].second+dp[i-j];
idx=j;
}
}
// cout << "max=" << idx;
// cout << en;
if(mx<dp[i-1]){
dp[i]=dp[i-1];
for(int j=1;j<=s;j++){
cnt[i][j]=cnt[i-1][j];
}
continue;
}
dp[i]=mx;
for(int j=1;j<=s;j++){
cnt[i][j]=cnt[i-idx][j];
// cout << cnt[i][j] << sp;
}
cnt[i][idx]++;
}
// for(int i=1;i<=s;i++){
// cout << i << (i<10?" : ":": ");
// for(int j=1;j<=s;j++){
// cout << cnt[i][j] << sp;
// }
// cout << en;
// }
// for(int i=1;i<=s;i++)cout << i << sp << dp[i] << en;
cout << dp[s] << en;
return 0;
}
