#include <bits/stdc++.h> using namespace std; const long long INF = 1e16; const int S = 2005; int s, n; vector<pair<int,int>> group[S], sum_group[S]; long long dp[S]; void input() { cin >> s >> n; for(int i = 1; i <= n; ++i) { int v, w, k; cin >> v >> w >> k; group[w].push_back({v, k}); } } long long get_val(int w, int t) { if(sum_group[w].size() == 0) return -1; if(sum_group[w].back().second < t) return -1; int low = 0, high = sum_group[w].size() - 1, pos = high; while(low <= high) { int mid = (low + high) / 2; if(sum_group[w][mid].second >= t) { pos = mid; high = mid - 1; } else { low = mid + 1; } } long long ans = 0; if(pos > 0) { ans += sum_group[w][pos - 1].first; t -= sum_group[w][pos - 1].second; } ans += 1ll * group[w][pos].first * t; return ans; } void solve() { for(int w = 1; w <= s; ++w) { sort(group[w].begin(), group[w].end(), greater<pair<long long,long long>>()); long long sum_v = 0, sum_k = 0; for(int i = 0; i < group[w].size(); ++i) { sum_v += 1ll * group[w][i].first * group[w][i].second; sum_k += 1ll * group[w][i].second; sum_group[w].push_back({sum_v, sum_k}); } } long long ans = 0; for(int x = 1; x <= s; ++x) dp[x] = -INF; dp[0] = 0; for(int w = 1; w <= s; ++w) { for(int x = s; x >= w; --x) { for(int t = 1; t <= x / w; ++t) { int old_x = x - w * t; if(dp[old_x] == -INF) continue; long long val = get_val(w, t); if(val == -1) break; // cerr << x << ' ' << w << ' ' << t << ' ' << val << endl; dp[x] = max(dp[x], dp[old_x] + val); } } } cout << *max_element(dp, dp + s + 1); } int main() { if(fopen("trash.inp" , "r")) freopen("trash.inp" , "r" , stdin) , freopen("trash.out" , "w" , stdout); ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); input(); solve(); }

knapsack.cpp: In function 'int main()':
knapsack.cpp:87:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |         freopen("trash.inp" , "r" , stdin) , freopen("trash.out" , "w" , stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:87:53: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |         freopen("trash.inp" , "r" , stdin) , freopen("trash.out" , "w" , stdout);
      |                                              ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~