#include <iostream> #include <vector> #include <algorithm> #include <deque> using namespace std; // Maximum capacity S is 2000 const int mxS = 2000; // We use long long for DP array to prevent overflow and handle -1e18 long long dp[mxS + 1]; // Structure for the item: Value, Weight, Quantity struct Item { long long v, w, k; }; int main() { // Fast I/O ios::sync_with_stdio(0); cin.tie(0); int s, n; cin >> s >> n; vector<Item> items(n); for (int i = 0; i < n; i++) { // Read value, weight, quantity cin >> items[i].v >> items[i].w >> items[i].k; } // Initialize DP array: dp[j] is the max value for capacity j. // Use a very small number for unreachable states. fill(dp, dp + mxS + 1, -1e18); dp[0] = 0; long long ans = 0; // --- Start Monotonic Queue Optimized Bounded Knapsack --- for (const auto& item : items) { long long v = item.v; long long w = item.w; long long k = item.k; // Iterate over all possible remainders 'r' modulo the item's weight 'w' for (long long r = 0; r < w && r <= s; r++) { // Deque stores pairs: {q, f(q)}, where f(q) = dp_old[r + q*w] - q*v // The deque is maintained to be monotonically decreasing in f(q). deque<pair<long long, long long>> q; // Iterate over all capacities j = r + q*w for (long long j = r; j <= s; j += w) { long long current_q = (j - r) / w; // 1. Calculate f(q) for the current capacity j long long f_q = dp[j] - current_q * v; // 2. Remove elements from the back that are worse (smaller f(q)) // than the current one (f_q) while (!q.empty() && q.back().second <= f_q) { q.pop_back(); } // Add the current {q, f(q)} to the back q.push_back({current_q, f_q}); // 3. Remove elements from the front that are outside the sliding window. // The window size is k. We need max f(q') where q' >= q - k. if (!q.empty() && q.front().first < current_q - k) { q.pop_front(); } // 4. Update the DP state using the maximum value in the queue (q.front().second) // dp_new[j] = max(f(q')) + q * v if (!q.empty() && dp[j] != -1e18) { // Only update if a valid state exists dp[j] = q.front().second + current_q * v; } } } } // --- End Monotonic Queue Optimized Bounded Knapsack --- // Find the overall maximum value for (int j = 0; j <= s; j++) { ans = max(ans, dp[j]); } cout << ans << endl; return 0; }