#include <bits/stdc++.h>
#define DEBUG false
using namespace std;
const int MAX_N = 2e3 + 10;
const int INF = 1e9 + 7;
vector <pair <int, int>> W[MAX_N];
long long dp[MAX_N][MAX_N];
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int S, N;
cin >> S >> N;
for(int i = 1; i <= N; i++) {
int v, w, k;
cin >> v >> w >> k;
W[w].emplace_back(v, k);
}
for(int i = 0; i <= S; i++) {
sort(W[i].begin(), W[i].end(), greater <pair <int, int>> ());
}
for(int i = 0; i <= S; i++) {
for(int j = 0; j <= S; j++) {
dp[i][j] = -INF;
}
}
dp[0][0] = 0;
for(int i = 1; i <= S; i++) {
for(int s = 0; s <= S; s++) {
dp[i][s] = dp[i - 1][s];
int ns = s;
long long nv = 0;
for(auto [v, k] : W[i]) {
int nk = k;
while(nk-- and ns - i >= 0) {
dp[i][s] = max(dp[i][s], dp[i - 1][ns - i] + nv + v);
nv += v;
ns -= i;
}
}
}
}
long long ans = 0;
for(int i = 0; i <= S; i++) {
ans = max(ans, dp[S][i]);
}
cout << ans;
return 0;
}
