#include <bits/stdc++.h>
using namespace std;
const int sx = 2001;
#define ll long long
int s, n;
vector<pair<ll,ll>> weight[sx];
ll dp[sx];
int main() {
ios_base::sync_with_stdio(0), cin.tie(0);
cin >> s >> n;
for (int i = 1; i <= n; i++) {
int v, w, k;
cin >> v >> w >> k;
weight[w].emplace_back(v, k);
}
for (int i = 1; i <= s; i++) dp[i] = -1e18, sort(weight[i].begin(),weight[i].end(),greater<pair<ll,ll>>());
for (int w = s; w >= 1; w--) {
if (weight[w].empty()) continue;
int need = s / w;
int ct = 0;
for (auto [v, k] : weight[w]) {
if (ct > need) break;
ct += k;
ll p = 1;
while (p <= k) {
ll nw = w * p, nv = v * p;
k -= p;
p *= 2;
for (int j = s; j >= nw; j--) dp[j] = max(dp[j], dp[j - nw] + nv);
}
if (k > 0) {
ll nw = w * k, nv = v * k;
for (int j = s; j >= nw; j--) dp[j] = max(dp[j], dp[j - nw] + nv);
}
}
}
ll ans = 0;
for (int i = 0; i <= s; i++) ans = max(ans, dp[i]);
cout << ans;
}
