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