#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int S, N; cin >> S >> N; vector<int> Weights(N), Values(N), Cnt(N); for (int i = 0; i < N; i++) { cin >> Values[i] >> Weights[i] >> Cnt[i]; } vector<pair<int,int>> items; for (int i = 0; i < N; i++) { int w = Weights[i]; int v = Values[i]; int c = Cnt[i]; int k = 1; while (c > 0) { int take = min(k, c); items.push_back({w * take, v * take}); c -= take; k *= 2; } } vector<int> dp(S + 1, 0); for (auto &[w, v] : items) { for (int j = S; j >= w; j--) { dp[j] = max(dp[j], dp[j - w] + v); } } cout << dp[S] << "\n"; return 0; }