#include <bits/stdc++.h> using namespace std; const int MAXS = 2005, MAXN = 1e5 + 5; const long long inf = 1e18 + 3; template<class X, class Y> bool maximize(X &x, const Y &y){return x < y ? x = y, 1: 0;} int numVal, lim, val[MAXN], weight[MAXN], num[MAXN], used[MAXS]; long long dp[MAXS]; void input(){ cin >> lim >> numVal; for(int i = 1; i <= numVal; i++) cin >> val[i] >> weight[i] >> num[i]; } void solve(){ memset(dp, -0x3f, sizeof dp); dp[0] = 0; for(int i = 1; i <= numVal; i++){ for(int j = 0; j <= lim; j++) used[j] = 0; for(int j = 0; j + weight[i] <= lim; j++) if (dp[j] > -inf){ if (used[j] < num[i]){ if (maximize(dp[j + weight[i]], dp[j] + val[i])) used[j + weight[i]] = used[j] + 1; } } } long long res = -inf; for(int i = 0; i <= lim; i++) maximize(res, dp[i]); cout << res << '\n'; } int main(){ input(); solve(); }