#include <bits/stdc++.h> using namespace std; int knapsack(int W, vector<int> &val, vector<int> &wt) { int n = wt.size(); vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0)); for (int i = 1; i <= n; i++) { for (int j = 0; j <= W; j++) { int pick = 0; if (wt[i - 1] <= j) pick = val[i - 1] + dp[i - 1][j - wt[i - 1]]; int notPick = dp[i - 1][j]; dp[i][j] = max(pick, notPick); } } return dp[n][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); return 0; }