#include <bits/stdc++.h> using namespace std; #define int long long int32_t main() { ios::sync_with_stdio(false); cin.tie(nullptr); int S, n; cin >> S >> n; vector<int> dp(S + 1, 0); for (int i = 1; i <= n; i++) { int v, w; long long k; cin >> v >> w >> k; long long power = 1; while (k > 0) { long long take = min(power, k); k -= take; int newWeight = take * w; int newValue = take * v; for (int j = S; j >= newWeight; j--) { dp[j] = max(dp[j], dp[j - newWeight] + newValue); } power *= 2; } } cout << *max_element(dp.begin(), dp.end()) << "\n"; return 0; }