#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<int> dp(S + 1, 0); for (int i = 0; i < N; ++i) { int w = Weights[i]; int v = Values[i]; int c = Cnt[i]; for (int j = S; j >= w; --j) { for (int k = 1; k <= c; ++k) { if (j - k * w < 0) break; dp[j] = max(dp[j], dp[j - k * w] + k * v); } } } cout << dp[S] << "\n"; return 0; }