#include <bits/stdc++.h> using namespace std; int knapsack(int W, vector<int> &val, vector<int> &wt) { vector<int> dp(W + 1, 0); for (int i = 1; i <= wt.size(); i++) { for (int j = W; j >= wt[i - 1]; j--) { dp[j] = max(dp[j], dp[j - wt[i - 1]] + val[i - 1]); } } return dp[W]; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, s; cin >> s >> n; vector<int> w, v; for (int i = 0; i < n; i++) { int vi, wi, ki; cin >> vi >> wi >> ki; int k = 1; while (ki >= k) { w.push_back(wi * k); v.push_back(vi * k); ki -= k; k <<= 1; } if (ki > 0) { w.push_back(wi * ki); v.push_back(vi * ki); } } cout << knapsack(s, v, w); }