#include<bits/stdc++.h>
#define For(i, x, n) for(int i = x; i < n; i++)
#define Rof(i, x, n) for(int i = n - 1; i >= x; i--)
#define IOS ios::sync_with_stdio(false); cin.tie(0);
#define F first
#define S second
#define pb push_back
#define po pop_back
#define En endl
#define endl "\n"
#define ALL(x) x.begin(), x.end()
#define RALL(x) x.rbegin(), x.rend();
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef vector<int> VI;
typedef vector<LL> VLL;
typedef vector<PLL> VPLL;
const int MN = 2e3 + 5;
const int MOD = 1e9 + 7;
const int LOG = 20;
const LL INF = 1e18 + 7;
LL s, n, v, maxw;
LL dp[MN][MN], k[MN], w[MN];
VLL keep[MN];
int main () {
IOS;
cin >> s >> n;
VPLL forsort;
For (i, 0, n) {
cin >> v >> w[i] >> k[i];
maxw = max(maxw, w[i]);
forsort.pb({v, i});
}
sort(ALL(forsort));
reverse(ALL(forsort));
for (PLL it : forsort) {
For (i, 0, k[it.S]) {
if (keep[w[it.S]].size() == MN - 5) break;
keep[w[it.S]].pb(it.F);
}
}
For (i, 0, maxw + 1) {
For (j, 1, s + 1) dp[i][j] = -INF;
}
For (i, 1, maxw + 1) {
For (j, 1, s + 1) {
dp[i][j] = dp[i - 1][j];
LL sum = 0;
For (k, 0, keep[i].size()) {
sum += keep[i][k];
LL jon = (k + 1) * i;
if (jon > j) break;
dp[i][j] = max(dp[i][j], dp[i - 1][j - jon] + sum);
}
}
}
cout << dp[maxw][s] << En;
/*
LL ans = 0;
For (j, 0, s + 1) ans = max(ans, dp[maxw][j]);
cout << ans << En;*/
}
