#include<bits/stdc++.h> using namespace std; #define ll long long const int mxS = 2005; // Slightly larger for safety ll dp[mxS]; int main() { ios::sync_with_stdio(0); cin.tie(0); int s, n; cin >> s >> n; // Use specific variables instead of array for readability and speed // dp array initialization fill(dp, dp + s + 1, -1e18); // Initialize only up to S dp[0] = 0; ll ans = 0; for(int i = 0; i < n; i++) { ll val, w, k; cin >> val >> w >> k; // Optimization: If weight is 0 or value is negative/useless, skip if (k == 0 || w == 0) continue; // HYBRID OPTIMIZATION START // If total weight of all copies exceeds capacity, treat as infinite (Complete Knapsack) if (w * k >= s) { for (int j = w; j <= s; j++) { if (dp[j-w] != -1e18) { dp[j] = max(dp[j], dp[j-w] + val); } ans = max(ans, dp[j]); } } // Otherwise, use your existing Binary Splitting method else { ll use = k; for (ll j = 1; use > 0; j *= 2) { ll take = min(use, j); ll weight_chunk = take * w; ll value_chunk = take * val; for (int pos = s; pos >= weight_chunk; pos--) { if (dp[pos - weight_chunk] != -1e18) { dp[pos] = max(dp[pos], dp[pos - weight_chunk] + value_chunk); } ans = max(ans, dp[pos]); } use -= take; } } // HYBRID OPTIMIZATION END } cout << ans; return 0; }