#include <algorithm> #include <iostream> #include <map> #include <vector> using namespace std; int main() { int weight_limit, num_types; cin >> weight_limit >> num_types; /* * Group items by their weight. * For each weight w: * we store (value, amount) */ map<int, vector<pair<int, int>>> items_by_weight; for (int i = 0; i < num_types; i++) { int value, weight, amount; cin >> value >> weight >> amount; if (weight <= weight_limit && amount > 0) { items_by_weight[weight].push_back({value, amount}); } } /* * dp[i][j] = maximum value achievable * using the first i distinct weights * with total weight exactly j * * i goes over weight groups, not individual items */ int W = items_by_weight.size(); vector<vector<long long>> dp( W + 1, vector<long long>(weight_limit + 1, -1e18) ); dp[0][0] = 0; // base case int group_index = 1; for (auto &[weight, items] : items_by_weight) { // Sort items of same weight by value (descending) sort(items.begin(), items.end(), greater<>()); for (int used_weight = 0; used_weight <= weight_limit; used_weight++) { // Option 1: take nothing from this weight group dp[group_index][used_weight] = dp[group_index - 1][used_weight]; long long gained_value = 0; int copies_taken = 0; int item_index = 0; int taken_from_item = 0; /* * Try taking 1, 2, 3, ... copies of this weight * while staying within weight limit */ while ((copies_taken + 1) * weight <= used_weight && item_index < items.size()) { copies_taken++; gained_value += items[item_index].first; taken_from_item++; if (dp[group_index - 1][used_weight - copies_taken * weight] >= 0) { dp[group_index][used_weight] = max( dp[group_index][used_weight], dp[group_index - 1][used_weight - copies_taken * weight] + gained_value ); } // Move to next item if current one is exhausted if (taken_from_item == items[item_index].second) { taken_from_item = 0; item_index++; } } } group_index++; } cout << *max_element(dp[W].begin(), dp[W].end()) << endl; }