#include <bits/stdc++.h> using namespace std; #define ll long long #define ld long double #define ull unsigned long long #define pll pair<ll, ll> #define ppll pair< pair<long long, long long>, long long > #define ff first #define ss second #define pb push_back #define pf push_front const ll DIM = 1e6 + 7; const ll INF = 1e18; const ll mod = 1e9 + 7; const ll maxlog = 20; const ll bsize = 350; ll dp[107][2007]; void solve() { ll s, n; cin >> s >> n; for (int i=1; i<=n; i++) { ll val, w, k; cin >> val >> w >> k; for (int nw=1; nw<=s; nw++) { for (int j=0; j<=min(k, s); j++) { if (nw < w*j) break; dp[i][nw] = max(dp[i][nw], dp[i-1][nw-w*j] + val*j); } } //for (int nw=0; nw<=s; nw++) cout << dp[i][nw] << " "; //cout << endl; } ll ans = 0; for (int i=s; i>=0; i--) { ans = max(ans, dp[n][i]); } cout << ans << endl; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int ntest = 1; //cin >> ntest; while (ntest--) { solve(); } return 0; } ;