#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int,int>;
#define FOR(i,a,b) for (int i=(a); i<=(b); ++i)
#define FORD(i,a,b) for (int i=(a); i>=(b); --i)
#define pb push_back
const int INF = 1e9;
const int MOD = 998244353;
const ll MOD2 = 1e9 + 7;
const ll LL_INF = 4e18;
const int MAXN = 1e6 + 1;
void solve() {
int s, n;
cin >> s >> n;
// obj[w] = list of (value, count) items with this weight w
vector<vector<pair<ll,ll>>> obj(s + 1);
FOR(i,1,n) {
ll v, w, k;
cin >> v >> w >> k;
if (w > s || k == 0) continue; // can't use these at all
obj[w].push_back({v, k});
}
vector<ll> dp(s + 1, 0);
// For each weight, process all items of that weight
FOR(w,1,s) {
auto &items = obj[w];
if (items.empty()) continue;
// Sort by value descending so we always use best-value items first
sort(items.begin(), items.end(),
[](const pair<ll,ll> &a, const pair<ll,ll> &b) {
return a.first > b.first;
});
int id = 0;
// We can use weight w at most s / w times in total (capacity limit)
for (int used = 0; used * w <= s; ++used) {
if (id >= (int)items.size()) break; // no more items of this weight
// Classic 0/1 knapsack transition for *one* copy of current item
for (int cap = s; cap >= w; --cap) {
dp[cap] = max(dp[cap], dp[cap - w] + items[id].first);
}
// Decrease remaining multiplicity; move to next item when exhausted
if (--items[id].second == 0) ++id;
}
}
// Problem version that AC'ed used dp[s] as answer:
cout << dp[s] << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int TC = 1;
// cin >> TC;
while (TC--) solve();
return 0;
}
