#include <iostream> #include <vector> #include <algorithm> #include <cmath> using namespace std; void solve() { ios_base::sync_with_stdio(false); cin.tie(NULL); int S, N; if (!(cin >> S >> N)) return; vector<int> Weights(N); vector<int> Values(N); vector<int> Cnt(N); for (int i = 0; i < N; ++i) { if (!(cin >> Values[i] >> Weights[i] >> Cnt[i])) return; } vector<pair<int, int>> items; for (int i = 0; i < N; ++i) { int w = Weights[i]; int v = Values[i]; int c = Cnt[i]; int k = 1; while (c > 0) { int take = min(k, c); 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; int v = item.second; for (int j = S; j >= w; --j) { dp[j] = max(dp[j], dp[j - w] + v); } } cout << dp[S] << endl; } int main() { solve(); return 0; }