#include <bits/stdc++.h>
#define int long long
using namespace std;
int dp[2001];
pair<pair<int,int>,int> a[2001];
int pref[3001][3001];
int lst[3001];
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int s, n; cin >> s >> n;
for(int i=0;i<n;i++){
cin >> a[i].first.first >> a[i].first.second;
cin >> a[i].second;
}
sort(a, a+n);
for(int i=n-1;i>=0;i--){
//cout << lst[a[i].first.second] << ' ';
for(int j = lst[a[i].first.second]+1; j<=min(s, lst[a[i].first.second]+a[i].second);j++){
pref[a[i].first.second][j]=pref[a[i].first.second][j-1];
pref[a[i].first.second][j]+=a[i].first.first;
}
lst[a[i].first.second]=min(s, lst[a[i].first.second]+a[i].second);
}
for(int i=1;i<=s;i++){
for(int j=s;j>=0;j--){
for(int x=lst[i]; x>=1; x--){
if(j+x*i<= s){
dp[j+x*i]=max(dp[j+x*i],dp[j]+pref[i][x]);
}
}
}
}
cout << *max_element(dp,dp+s+1) << '\n';
return 0;
}
