#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 v, w, k; cin >> v >> w >> k; if (w <= S && w > 0) { k = min(k, (long long)S / w); if (k > 0) groups[w].push_back({(int)v, k}); } } vector<long long> dp(S + 1, 0); for (int w = 1; w <= S; ++w) { if (groups[w].empty()) continue; sort(groups[w].rbegin(),groups[w].rend()); vector<int> values; for (auto &p : groups[w]) { int val = p.first; long long cnt = p.second; for (int t = 0; t < cnt && (int)values.size() < S / w; ++t) { values.push_back(val); } } sort(values.rbegin(), values.rend()); for (int val : values) { for (int cap = S; cap >= w; --cap) { dp[cap] = max(dp[cap], dp[cap - w] + val); } } } cout << dp[S] << "\n"; return 0; }