#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define sp << " " <<
#define int long long
#define vi vector<int>
#define pb push_back
#define F(xxx,yyy) for (int xxx=1;xxx<=yyy;xxx++)
#define pii pair<int,int>
#define ordered_set tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update>
const int MOD = 1e9+9;
int add(int x,int y) {return ((x%MOD)+(y%MOD))%MOD;}
void solve() {
int n,s;
cin >> s >> n;
priority_queue<pii> items[s+1];
vi sz(s+1,0);
F(i,n) {
int v,w,q;
cin >> v >> w >> q;
items[w].push({v,q});
sz[w]+=q;
}
vector<vi> dp(s+1,vi(s+1,-2e18));
vector<vi> c(s+1,vi(s+1,0));
for (int i=1;i<=s;i++) {
int got = 0;
int taken = 0;
c[i][0] = 0;
for (int j=1;i*j<=s;j++) {
if (items[i].empty()) break;
got+=items[i].top().first;
taken++;
c[i][j] = got;
if (taken == items[i].top().second) {
taken = 0;
items[i].pop();
}
}
}
dp[0][0] = 0;
F(i,s) {
for (int j=0;j<=s;j++) {
for (int take = 0;take<=sz[i] && take*i+j<=s;take++) {
dp[i][j+take*i] = max(dp[i][j+take*i],dp[i-1][j]+c[i][take]);
}
}
}
cout << *max_element(dp[s].begin(),dp[s].end()) << endl;
}
signed main() {
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int t = 1;
//cin >> t;
while (t --> 0) solve();
}
