#include <bits/stdc++.h> using namespace std; #define ll long long const ll MAXN=1e5+5; const ll MAXS=2005; ll s, n, v[MAXN], w[MAXN], k[MAXN], dp[MAXS], ans; void dodp(ll vx, ll wx) { for (int i=s; i>=wx; i--) { dp[i]=max(dp[i], dp[i-wx]+vx); } } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cin >> s >> n; for (int i=0; i<n; i++) { cin >> v[i] >> w[i] >> k[i]; ll m=1; while (k[i]>0) { m=min(m, k[i]); dodp(v[i]*m, w[i]*m); k[i]-=m; m*=2; } } for (int i=1; i<=s; i++) { ans=max(ans, dp[i]); } cout << ans << "\n"; }