#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define debug(a) cout << #a << " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "
#define lli long long int
#define rep(i,a,b) for(int i = (a); i <= (b); i++)
#define repa(i,a,b) for(int i = (a); i >= (b); i--)
#define pb push_back
#define MAX 2000
#define valor first
#define cant second
lli s,n,a,b,c,umbral,contador;
vector<pair<lli,lli> > peso[MAX+2];
lli dp[MAX+2];
void solve(lli dis, lli costo) {
repa(i,s,dis) {
dp[i] = max(dp[i], dp[i-dis] + costo);
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> s >> n;
rep(i,1,n) {
cin >> a >> b >> c;
peso[b].pb({a,c});
}
rep (i,1,s) {
if (peso[i].empty()) continue;
sort(peso[i].begin(), peso[i].end());
reverse(peso[i].begin(), peso[i].end());
umbral = s/i;
contador = 0;
for (auto act : peso[i]) {
rep(j,1,act.cant) {
contador++;
if (contador > umbral) break;
solve(i,act.valor);
}
if (contador > umbral) break;
}
}
cout << dp[s];
}
