#include <iostream> #include <vector> #include <algorithm> #define rep(i, s, e) for (ll i = s; i < e; i++) #define upmax(a, b) a = max(a, b) using namespace std; using ll = long long; using vll = vector<ll>; using vvll = vector<vll>; void solve() { ll n, S; cin >> S >> n; vll v(n), w(n), k(n); rep(i, 0, n) { cin >> v[i] >> w[i] >> k[i]; } vll dp(S + 1); dp[0] = 0; rep(numC, 1, k[0] + 1) { if (numC * w[0] > S) { break; } dp[numC * w[0]] = numC * v[0]; } rep(i, 1, S + 1) upmax(dp[i], dp[i - 1]); rep(i, 1, n) { vll nextdp(S + 1); nextdp[0] = 0; rep(j, 1, S + 1) { rep(numC, 0, k[i] + 1) { if (j - numC * w[i] < 0) { break; } upmax(nextdp[j], dp[j - numC * w[i]] + numC * v[i]); } } swap(dp, nextdp); } /* vvll dp(n, vll(S + 1)); rep(i, 0, n) dp[i][0] = 0; rep(numC, 1, k[0] + 1) { if (numC * w[0] > S) { break; } dp[0][numC * w[0]] = numC * v[0]; } rep(i, 1, S + 1) upmax(dp[0][i], dp[0][i - 1]); rep(i, 1, n) { rep(j, 1, S + 1) { rep(numC, 0, k[i] + 1) { if (j - numC * w[i] < 0) { break; } upmax(dp[i][j], dp[i - 1][j - numC * w[i]] + numC * v[i]); } } }*/ cout << dp[S] << endl; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); solve(); }