#include <bits/stdc++.h>
using namespace std;
template<class A, class B> bool maximize(A& x, B y) {if (x < y) return x = y, true; else return false;}
template<class A, class B> bool minimize(A& x, B y) {if (x > y) return x = y, true; else return false;}
#define all(a) a.begin(), a.end()
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define int long long
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ld;
typedef pair<db, db> pdb;
typedef pair<ld, ld> pld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> plli;
typedef pair<int, ll> pill;
int s, n;
vector<pii> a[2001];
vector<pii> b;
int dp[2002];
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> s >> n;
for (int i = 1; i <= n; i++) {
int v, w, k;
cin >> v >> w >> k;
a[w].pb({v, k});
}
priority_queue<pii> pq;
for (int i = 1; i <= s; i++) {
while (!pq.empty()) pq.pop();
for (auto it : a[i]) {
pq.push(it);
}
int lim = 2000 / i;
while (lim && !pq.empty()) {
auto it = pq.top();
pq.pop();
b.pb({it.fi, i});
it.se--;
lim--;
if (it.se) {
pq.push(it);
}
}
}
for (auto it : b) {
for (int i = s; i; i--) {
if (it.se <= i) {
maximize(dp[i], dp[i - it.se] + it.fi);
}
}
}
cout << dp[s];
return 0;
}
/*
*/
