#include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int S, N; if (!(cin >> S >> N)) return 0; vector<long long> Values(N); vector<int> Weights(N); vector<int> Cnt(N); for (int i = 0; i < N; ++i) { cin >> Values[i] >> Weights[i] >> Cnt[i]; } vector<pair<int, long long>> items; for (int i = 0; i < N; ++i) { int w = Weights[i]; long long v = Values[i]; int c = Cnt[i]; int k = 1; while (c > 0) { int take = min(k, c); if ((long long)w * take <= S) { items.push_back({w * take, v * take}); } c -= take; k *= 2; } } vector<long long> dp(S + 1, 0); for (const auto& item : items) { int w = item.first; long long v = item.second; for (int j = S; j >= w; --j) { dp[j] = max(dp[j], dp[j - w] + v); } } cout << dp[S] << endl; return 0; }