#include <bits/stdc++.h> using namespace std; #define ll long long #define FASTIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0) struct Item { ll v, w; }; void solve() { int s, n; cin >> s >> n; vector<Item> items; for (int i = 0; i < n; ++i) { ll v, w, k; cin >> v >> w >> k; ll currentK = k; ll count = 1; while (currentK > 0) { ll num = min(currentK, count); items.push_back({v * num, w * num}); currentK -= num; count *= 2; } } vector<ll> dp(s + 1, 0); for (const auto& item : items) { ll v = item.v; ll w = item.w; for (int cw = s; cw >= w; --cw) { dp[cw] = max(dp[cw], dp[cw - w] + v); } } ll maxVal = 0; for (int cw = 0; cw <= s; ++cw) { maxVal = max(maxVal, dp[cw]); } cout << maxVal << endl; } int main() { FASTIO; solve(); return 0; }