#include <iostream> #include <vector> #include <algorithm> #include <cmath> using namespace std; struct Item { int weight; int value; }; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int S, N; if (!(cin >> S >> N)) return 0; vector<int> Weights(N); vector<int> Values(N); vector<int> Cnt(N); for (int i = 0; i < N; ++i) { cin >> Values[i] >> Weights[i] >> Cnt[i]; } vector<Item> 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<int> dp(S + 1, 0); for (const auto& item : items) { int w = item.weight; int v = item.value; for (int j = S; j >= w; --j) { dp[j] = max(dp[j], dp[j - w] + v); } } cout << dp[S] << "\n"; return 0; }