#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int S, N; cin >> S >> N; vector<vector<pair<int,long long>>> groups(S + 1); for (int i = 0; i < N; ++i) { long long Vi, Wi, Ki; cin >> Vi >> Wi >> Ki; if (Wi <= S) groups[Wi].push_back({(int)Vi, Ki}); } vector<long long> dp(S + 1, 0); for (int w = 1; w <= S; ++w) { if (groups[w].empty()) continue; auto &vec = groups[w]; sort(vec.begin(), vec.end(), [](const pair<int,long long>& a, const pair<int,long long>& b){ return a.first > b.first; }); int limit = S / w; vector<long long> single; single.reserve(limit); for (auto &p : vec) { long long val = p.first; long long cnt = p.second; long long can_take = min<long long>(cnt, limit - (int)single.size()); for (long long t = 0; t < can_take; ++t) single.push_back(val); if ((int)single.size() == limit) break; } if (single.empty()) continue; int m = single.size(); vector<long long> pref(m + 1, 0); for (int i = 0; i < m; ++i) pref[i + 1] = pref[i] + single[i]; for (int t = 1; t <= m; ++t) { int wt = t * w; long long val = pref[t]; for (int cap = S; cap >= wt; --cap) { dp[cap] = max(dp[cap], dp[cap - wt] + val); } } } cout << dp[S] << "\n"; return 0; }