#include <bits/stdc++.h>
#define pi pair<int, int>
#define x first
#define y second
#define pb push_back
#define mp make_pair
using namespace std;
int main(){
int s, n; cin >> s>>n;
vector<pi> stuff[s+1];
int dp[s+1][s+1];
for(int i=0; i<=s; i++)for(int j=0; j<=s; j++) dp[i][j] =0;
for(int i=0; i<n; i++){
int a,b,c; cin >> a>>b>>c;
if(b>s) continue;
stuff[b].pb(mp(a,c));
}
for(int i=0; i<=s; i++) sort(stuff[i].begin(), stuff[i].end());
int ever = 0;
for(int i=1; i<=s; i++)for(int j=1; j<=s; j++){
dp[i][j] = dp[i][j-1];
int sum = 0, val = 0;
for(int p = stuff[j].size()-1; p>=0; p-- ){
pi elem = stuff[j][p];
for(int t=1; t<=elem.y; t++){
sum += j;
val += elem.x;
if(sum > i) break;
dp[i][j] = max(dp[i][j], dp[i-sum][j-1] + val);
ever =max(ever, dp[i][j]);
}
if(sum > i) break;
}
}
cout << ever;
}
