/* * * author: attacker * * created: 27.01.2026 16:54:50 */ #include <bits/stdc++.h> using namespace std; #ifdef LOCAL #include "algo/debug.h" #else #define debug(...) 42 #endif #define mt_rng mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int n; int64_t lim; cin >> lim >> n; vector<int64_t> v; vector<int64_t> w; for (int i = 0; i < n; i++) { int64_t cur_v, cur_w; int cnt; cin >> cur_v >> cur_w >> cnt; for (int id = 0; id < cnt; id++) { v.push_back(cur_v); w.push_back(cur_w); } } const int64_t inf = int64_t(1e18); vector<int64_t> dp(lim + 1, -inf); dp[0] = 0; for (int i = 0; i < n; i++) { for (int64_t j = lim; j >= w[i]; j--) { dp[j] = max(dp[j], dp[j - w[i]] + v[i]); } } cout << dp[lim] << '\n'; return 0; }