#include <bits/stdc++.h>
#define int long long
#define f first
#define s second
#define pb push_back
#define endl '\n'
using namespace std;
int S,N,V,W,K,dp[2005],ans;
vector<vector<pair<int, int>>> v(2005);
vector<pair<int, int>> kp;
void solve() {
cin >> S >> N;
dp[0] = 0;
for (int i = 1; i <= S; i++) dp[i] = -1e9;
for (int i = 1; i <= N; i++) {
cin >> V >> W >> K;
v[W].pb({V, K});
} // instead of compress with with W and K, why not W only?
for (int w = 1; w <= 2000; w++) {
sort(v[w].rbegin(), v[w].rend());
int Wmx = 2000;
for (auto &cur : v[w]) {
if (Wmx - w < 0) break;
while (Wmx - w >= 0 && cur.s) {
kp.pb({w, cur.f});
Wmx -= w;
cur.s--;
}
}
}
for (auto cur : kp) {
W = cur.f;
V = cur.s;
// cout << W << ' ' << V << endl;
for (int j = S; j >= W; j--) dp[j] = max(dp[j], dp[j - W] + V);
}
for (int i = 0; i <= S; i++) ans = max(ans, dp[i]);
cout << ans << endl;
}
int32_t main() {
ios_base::sync_with_stdio(0); cin.tie(0);
int tttt = 1;
//cin >> tttt;
while (tttt--) solve();
}
