#include <bits/stdc++.h> using namespace std; // ====== Short types ====== #define ll long long #define ld long double #define str string #define pll pair<ll, ll> #define pii pair<int, int> #define vll vector<ll> #define vii vector<int> #define vld vector<ld> #define vs vector<string> #define vch vector<char> #define vpll vector<pll> #define vpii vector<pii> #define mll map<ll, ll> #define msl map<string, ll> #define mcl map<char, ll> #define sll set<ll> #define scl set<char> #define ssl set<string> // ====== Common macros ====== #define pb push_back #define ppb pop_back #define ff first #define ss second #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() #define sz(x) (int)((x).size()) #define mpr make_pair #define bk back #define rtn return #define ctn continue #define brk break // ====== Algorithms ====== #define uniq(x) x.erase(unique(all(x)), x.end()) // works only after sorting #define sortv(v) sort(all(v)) #define rsortv(v) sort(rall(v)) #define maxv(v) *max_element(all(v)) #define minv(v) *min_element(all(v)) #define sumv(v) accumulate(all(v), 0LL) #define rev(v) reverse(all(v)) #define lb lower_bound #define ub upper_bound // ====== Loops ====== #define forr(i, n) for (ll i = 0; i < (n); i++) #define rforr(i, n) for (ll i = (n)-1; i >= 0; i--) #define forab(i, a, b) for (ll i = (a); i <= (b); i++) #define forba(i, a, b) for (ll i = (a); i >= (b); i--) // ====== Input Shortcuts ====== #define cn(n) ll n; cin >> n; #define cna(a, b) ll a, b; cin >> a >> b; #define cna3(a, b, c) ll a, b, c; cin >> a >> b >> c; #define cna4(a, b, c, d) ll a, b, c, d; cin >> a >> b >> c >> d; // ====== String Shortcuts ====== #define cs(s) string s; cin >> s; #define csa(a, b) string a, b; cin >> a >> b; #define csa3(a, b, c) string a, b, c; cin >> a >> b >> c; #define csa4(a, b, c, d) string a, b, c, d; cin >> a >> b >> c >> d; // ====== IO helpers ====== #define fastio ios::sync_with_stdio(false); cin.tie(nullptr); #define nl '\n' #define ct cout #define YES ct << "YES\n" #define NO ct << "NO\n" #define Yes ct << "Yes\n" #define No ct << "No\n" #define YN(x) ct << ((x) ? "YES\n" : "NO\n") #define yn(x) ct << ((x) ? "Yes\n" : "No\n") // ====== Debugging ====== #define debug(x) cerr << #x << " = " << (x) << '\n' #define debugv(v) cerr << #v << ": "; for (auto _x : v) cerr << _x << " "; cerr << '\n' // ====== Miscellaneous ====== #define ins insert #define ers erase #define cntv count #define fnd find #define bg begin #define ed end // ====== Constants ====== const ll INF = 1e18; const ll MOD = 1e9 + 7; const ll MOD2 = 998244353; const ll N = 1e6 + 5; const ld EPS = 1e-9; const ld PI = acos(-1.0); const ll ngmx = -1e18; // ====== Input/Output Helpers ====== template<typename T> void cinv(vector<T> &v, ll n) { v.resize(n); forr(i, n) cin >> v[i]; } template<typename T> void cinvv(vector<vector<T>> &v, ll n, ll m) { v.assign(n, vector<T>(m)); forr(i, n) forr(j, m) cin >> v[i][j]; } template<typename T> void ctv(const vector<T> &v, char sep = ' ') { for (auto &x : v) ct << x << sep; ct << '\n'; } template<typename T> void ctvv(const vector<vector<T>> &v) { for (auto &row : v) ctv(row); } // ====== Math Helpers ====== ll gcdll(ll a, ll b) { return b ? gcdll(b, a % b) : a; } ll lcmll(ll a, ll b) { return a / gcdll(a, b) * b; } #define powmod bigmod ll bigmod(ll a, ll b, ll m = MOD) { ll r = 1; a %= m; while (b) { if (b & 1) r = (r * a) % m; a = (a * a) % m; b >>= 1; } return r; } ll addmod(ll a, ll b, ll m = MOD) { a += b; if (a >= m) a -= m; return a; } ll submod(ll a, ll b, ll m = MOD) { a -= b; if (a < 0) a += m; return a; } ll mulmod(ll a, ll b, ll m = MOD) { return (a * 1LL * b) % m; } ll invmod(ll a, ll m = MOD) { return bigmod(a, m - 2, m); } // Fermat’s inverse (for prime mod) // ====== Prime & Sieve ====== vector<ll> primes; vector<bool> isprime(N, true); void sieve(ll n = N - 1) { isprime[0] = isprime[1] = false; for (ll i = 2; i * i <= n; i++) if (isprime[i]) for (ll j = i * i; j <= n; j += i) isprime[j] = false; for (ll i = 2; i <= n; i++) if (isprime[i]) primes.pb(i); } bool isPrime(ll n) { if (n < 2) return false; for (ll i = 2; i * i <= n; i++) if (n % i == 0) return false; return true; } // ====== Combinations ====== vll fact(N), invfact(N); void init_fact(ll n = N - 1) { fact[0] = 1; forab(i, 1, n) fact[i] = (fact[i - 1] * i) % MOD; invfact[n] = invmod(fact[n]); forba(i, n - 1, 0) invfact[i] = (invfact[i + 1] * (i + 1)) % MOD; } ll nCr(ll n, ll r) { if (r < 0 || r > n) return 0; return (((fact[n] * invfact[r]) % MOD) * invfact[n - r]) % MOD; } // // Precompute primes and factorials // sieve(); // init_fact(); // ====== Bit Helpers ====== #define bitcount(x) __builtin_popcountll(x) #define clz(x) __builtin_clzll(x) #define ctz(x) __builtin_ctzll(x) void solve() { ll n , s; cin >> s >> n; vll dp(s + 1 , 0); forr(o , n){ ll v , w , cnt; cin >> v >> w >> cnt; ll tot = 0; forr(j , cnt){ tot += w; forba(i , s , tot){ dp[i] = max(dp[i] , dp[i - tot] + v * (j + 1)); } } } /* 9 1 2 4 2 */ ct << maxv(dp); } // ====== Main ====== int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int t = 1; // cin >> t; while (t--) { solve(); //YN(solve()); // cout<<solve()<<endl; } return 0; }