// Problem: Minimizing Coins
// Contest: CSES - CSES Problem Set
// URL: https://cses.fi/problemset/task/1634
// Memory Limit: 512 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
typedef long long int64;
#define V vector
#define P pair
#define pb push_back
#define epb emplace_back
#define endll "\n"
namespace config {
void io() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
}
namespace oldsolution {
void main() {
// we cant literally just push back every single copy for all K for an item
// try to group them together?
// no but then it might lead to innacurate knapsack logic later
// bundle with binary decomposition?
// so weight 13 = 1 + 4 + 8
int weightLimit, n;
cin >> weightLimit >> n;
V<int> weights, values;
for (int i = 0; i < n; i++) {
int value, weight, quantity;
cin >> value >> weight >> quantity;
int power = 1;
while (quantity > 0) {
int chunk = min(power, quantity);
quantity -= chunk;
int newWeight = weight * chunk;
int newValue = value * chunk;
weights.pb(newWeight);
values.pb(newValue);
power <<= 1;
}
}
// ok so now this is just a classical 0/1 knapsack
// dp[i] is the most value for a certain weight limit i
V<int> dp(weightLimit + 1, 0);
// base case:
// the most value for a weight limit of 0 would be 0
// this is already there since I initialized the whole vector to 0s
// outside loop: iterate over items
const int numItems = weights.size();
for (int item = 0; item < numItems; item++) {
for (int currentWeightLimit = weightLimit; currentWeightLimit >= weights[item]; currentWeightLimit--) {
dp[currentWeightLimit] = max(dp[currentWeightLimit], dp[currentWeightLimit - weights[item]] + values[item]);
}
}
cout << dp[weightLimit] << endll;
// THIS SOLUTION DID NOT WORK BECAUSE OF RUNTIME ERRORS, BUT IT WAS PARTIALLY RIGHT
}
}
namespace solution {
void main() {
int weightLimit, n;
cin >> weightLimit >> n;
map<int, V<P<int, int>>> itemsByWeight; // <weight, <value, quantity>>
for (int i = 0; i < n; i++) {
int value, weight, quantity;
cin >> value >> weight >> quantity;
if (weight <= weightLimit) {
itemsByWeight[weight].epb(value, quantity);
}
}
// sort in descending order
for (auto& [weight, items] : itemsByWeight) {
sort(items.begin(), items.end(), [](const P<int, int>& a, const P<int, int>& b) {
return a.first > b.first;
});
}
V<V<int64>> dp(itemsByWeight.size() + 1, V<int64>(weightLimit + 1, INT32_MIN));
// dp[i][j]
// i -> groups processed so far : [0, num of groups]
// j -> current total weight limit : [0, weight limit]
dp[0][0] = 0;
int groupIndex = 1;
for (auto& [weight, items] : itemsByWeight) {
// already sorted in decreasing order
for (int cap = 0; cap <= weightLimit; cap++) { // its 2D dp so yes were going up
// dont take anything from this weight grp
dp[groupIndex][cap] = dp[groupIndex - 1][cap];
// take some items from this weight grp
int64 totalValue = 0;
int copies = 0;
int typeIndex = 0; // index in items vector
int usedFromType = 0; // for the current (val, quantity)
while ((copies + 1) * weight <= cap && typeIndex < items.size()) {
copies++;
// add this items value
totalValue += items[typeIndex].first;
if (dp[groupIndex - 1][cap - copies * weight] != INT32_MIN) {
dp[groupIndex][cap] = max(dp[groupIndex][cap], dp[groupIndex - 1][cap - copies * weight] + totalValue);
}
usedFromType++;
if (usedFromType == items[typeIndex].second) { // if I've used up all of the copies for this guy
usedFromType = 0;
typeIndex++;
}
}
}
groupIndex++;
}
int64 ans = 0;
for (int cap = 0; cap <= weightLimit; cap++) {
ans = max(ans, dp[groupIndex - 1][cap]);
}
cout << ans << endll;
}
}
int main() {
config::io();
solution::main();
return 0;
}
