#include<bits/stdc++.h>
#define FOR(i, l, r) for(int i = (l), _r = (r); i <= _r; ++i)
#define FOD(i, l, r) for(int i = (l), _r = (r); i >= _r; --i)
#define REP(i, n) for(int i = 1; i <= (n); ++i)
#define RED(i, n) for(int i = n; i >= 1; --i)
#define ll long long
#define ALL(a) a.begin(), a.end()
#define sz(a) a.size()
#define file(name) if(fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);}
#define el "\n"
#define bit(a, x) (a >> x & 1)
#define X first
#define Y second
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
#define pb push_back
#define cntbit(x) __builtin_popcountll(x)
#define uni(a) sort(ALL(a)), a.resize(unique(ALL(a)) - a.begin())
using namespace std;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef vector<int> vi;
const int maxn = 2005;
ll dp[2005];
vector<pii> a[maxn];
int s, n, v, w, k;
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> s >> n;
FOR(i, 1, n){
cin >> v >> w >> k;
a[w].pb({v, k});
}
ll ans = 0;
FOR(i, 1, s){
sort(ALL(a[i]), greater<pii> ());
int id = 0;
FOR(j, 1, s / i){
if(id >= sz(a[i])) break;
FOD(k, s, i){
dp[k] = max(dp[k], dp[k - i] + a[i][id].X);
ans = max(ans, dp[k]);
}
a[i][id].Y--;
if(a[i][id].Y == 0) ++id;
}
}
//FOR(i, 1, s) cout << dp[i] << ' ';
cout << ans;
cerr << "Time elapsed: " << TIME << " s" << el;
}
