#include <bits/stdc++.h>
using namespace std;
#define OPTM ios_base::sync_with_stdio(0); cin.tie(0);
#define INF int(1e9+7)
#define ln '\n'
#define ll long long
#define ull unsigned long long
#define ui unsigned int
#define us unsigned short
#define FOR(i,s,n) for (int i = s; i < n; i++)
#define FORR(i,n,s) for (int i = n; i > s; i--)
#define FORX(u, arr) for (auto u : arr)
#define PB push_back
#define in(v,x) (v.find(x) != v.end())
#define F first
#define S second
#define PII pair<int, int>
#define UM unordered_map
#define US unordered_set
#define PQ priority_queue
#define ALL(v) v.begin(), v.end()
const ll LLINF = 1e18+1;
const int MAXN = 1e5+1, MAXS = 2e3+1;
int n,s;
vector<pair<ll,int>> a[MAXS], b;
ll dp[2][MAXS];
signed main() {
OPTM;
cin >> s >> n;
FOR(i,0,n) {
ll v; int w,k;
cin >> v >> w >> k;
a[w].PB({v,k});
}
FOR(i,1,s+1) {
int an = a[i].size();
sort(ALL(a[i]), greater<pair<ll,int>>());
int j = 0, l = 0;
while (j < an && l < s) {
if (a[i][j].S > 0) {
b.PB({a[i][j].F, i});
l += i;
a[i][j].S--;
}
else j++;
}
}
int bn = b.size();
FOR(i,0,bn) {
FOR(j,0,s+1) {
dp[1][j] = dp[0][j];
if (j >= b[i].S) dp[1][j] = max(dp[1][j], dp[0][j-b[i].S]+b[i].F);
}
FOR(j,0,s+1) {
dp[0][j] = dp[1][j];
dp[1][j] = 0;
}
}
cout << dp[0][s];
}
