#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define F first
#define S second
using namespace std;
const int N = 3e5+10;
const int mod = 1e9+7;
const int inf = 1e18;
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int s,n;
cin >> s >> n;
vector<int>v(n+1),w(n+1),k(n+1);
vector<pair<int,int>>g[s+1];
for(int i=1;i<=n;i++) {
cin >> v[i] >> w[i] >> k[i];
g[w[i]].pb({v[i],k[i]});
}
for(int i=1;i<=s;i++) {
sort(g[i].begin(),g[i].end());
reverse(g[i].begin(),g[i].end());
}
vector<pair<int,int>>V;
for(int i=1;i<=s;i++) {
int mx = s/i;
for(auto X:g[i]) {
if(mx < 0) break;
for(int j=1;j<=X.S;j++) {
V.pb({X.F,i});
mx -= 1;
if(mx == -1) break;
}
}
}
vector<int>dp(s+1);
for(auto X:V) {
vector<int>new_dp = dp;
for(int i=1;i<=s;i++) if(i >= X.S) new_dp[i] = max(new_dp[i],dp[i-X.S]+X.F);
swap(dp,new_dp);
}
cout << dp[s];
return 0;
}
