#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> p32;
typedef pair<ll, ll> p64;
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define vi vector<int>
#define vp32 vector<p32>
#define fast_cin() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define MOD %1000000007
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<class T>
using Tree =
tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
//never guess
//never debug without reviewing code
//never try adding ones or substracting them
//only step by step debug when necessay
#define int ll
signed main() {
fast_cin();
int s, n;
cin >> s >> n;
vp32 vp[s+1];
for (int i = 0; i < n; i++) {
int v, w, k;
cin >> v >> w >> k;
vp[w].eb(v, k);
}
int dp[s+1];
fill(dp,dp+s+1,INT_MIN);
dp[0] = 0;
for (int i = 1; i <= s; i++) {
if(vp[i].empty()) continue;
sort(vp[i].begin(), vp[i].end());
int weight = i;
int cur = 0;
int cnt = 0;
auto ii = vp[i].rbegin();
vector<vi> res(s,vi(s+1));
while (weight <= s) {
if (cnt >= ii->se) {
ii++;
if(ii==vp[i].rend())break;
cnt = 0;
}
cur+=ii->fi;
for(int j = 0; j<=s; j++) res[cnt][j] = dp[j];
for(int j = 0; j<=s-weight; j++){
res[cnt][j+weight] = max(res[cnt][j+weight],dp[j]+cur);
}
if(cnt) for(int j = 0; j<=s; j++) res[cnt][j] = max(res[cnt][j],res[cnt-1][j]);
cnt++;
weight += i ;
}
for(int j = 0; j<=s; j++) dp[j] = res[cnt-1][j];
}
for(int i = 1; i<=s; i++){
dp[i] = max(dp[i],dp[i-1]);
}
cout<<dp[s]<<'\n';
return 0;
}
