#include <bits/stdc++.h> using namespace std; using ll = long long; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int S, n; if (!(cin >> S >> n)) return 0; vector<vector<pair<int,long long>>> E(S + 1); for (int i = 0; i < n; ++i) { int v, w; long long k; cin >> v >> w >> k; if (w <= S) E[w].push_back({v, k}); } vector<long long> dp_prev(S + 1, 0), dp_curr; for (int weight = 1; weight <= S; ++weight) { dp_curr = dp_prev; for (auto &it : E[weight]) { long long val = it.first; long long cnt = it.second; long long takePow = 1; while (cnt > 0) { long long take = min(takePow, cnt); cnt -= take; int wtot = int(take * weight); long long vtot = val * take; for (int cap = S; cap >= wtot; --cap) { dp_curr[cap] = max(dp_curr[cap], dp_curr[cap - wtot] + vtot); } takePow <<= 1; } } dp_prev.swap(dp_curr); } long long ans = 0; for (int c = 0; c <= S; ++c) ans = max(ans, dp_prev[c]); cout << ans << '\n'; return 0; }