#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
const ll LOG = 31;
const ll MOD = 1000000007;
const ll inf = 1e17;
#define db(x) cerr << #x << " = " << x << " | "
#define dbg(x) cerr << #x << " = " << x << "\n"
#define Algerian ios::sync_with_stdio(0);
#define OI cin.tie(NULL);
int main() {
Algerian OI
ll s, n;
cin >> s >> n;
vector<ll> k(n), v(n), w(n);
vector<vector<ll>> weights(s + 1);
for (ll i = 0; i < n; i++) {
cin >> v[i] >> w[i] >> k[i];
weights[w[i]].push_back(i);
}
vector<ll> dp(s + 1, 0);
for (ll i = 1; i <= s; i++) {
sort(weights[i].begin(), weights[i].end(), [&](ll a, ll b) -> bool {
return v[a] > v[b];
});
}
for (ll i = 1; i <= s; i++) {
for (ll wt = s - 1; wt >= 0; wt--) {
ll val = dp[wt];
// ll cnt = 0;
ll cur_wt = wt;
for (ll j = 0; j < weights[i].size() && cur_wt + i <= s; j++) {
for (ll amt = 1; amt <= k[weights[i][j]] && cur_wt + i <= s; amt++) {
val += v[weights[i][j]];
cur_wt += i;
dp[cur_wt] = max(dp[cur_wt], val);
}
// ll get = min(k[weights[i][j]], (s - cur_wt) / i);
// val += v[weights[i][j]] * get;
// if (i == 1 && wt == 0) {
// dbg(get);
// dbg(v[weights[i][j]]);
// }
// cur_wt += get * i;
// dp[cur_wt] = max(dp[cur_wt], val);
}
}
}
ll res = 0;
for (ll i = 0; i <= s; i++) res = max(res, dp[i]);
// dbg(dp[5]);
cout << res << "\n";
return 0;
}
