#include <bits/stdc++.h> #include <cstdio> using namespace std; typedef long long ll; typedef pair<int,int> pii; typedef long double ld; typedef pair<ll,ll> pll; #define forr(i,a,b) for(int i=(int)(a);i<=(int)(b);i++) #define forf(i,a,b) for(int i=(int)(a);i<(int)(b);i++) #define ford(i,a,b) for(int i=(int)(a);i>=(int)(b);i--) #define REP(i,v) for(auto i: v) #define fi first #define se second #define pb push_back #define all(x) begin(x),end(x) #define MASK(i) (1LL<<i) #define bit(x,i) ((x<<iLL)&1) #define file "A" const int N= 2e5+5; const int mod= 1e9+7; const ll oo= (ll) 1e16; int n,w; ll dp[N]; vector<pll> items; void solve() { cin>>w>>n; forr(i,1,n) { int x,y,z; cin>>y>>x>>z; int k=1; while (z>k) { if (1LL*x*k>(ll) w) break; items.pb({x*k,y*k}); z-=k; k*=2; } if (z) items.pb({x*z,y*z}); } memset(dp,-63,sizeof(dp)); dp[0]=0; for(pii x: items) { ford(i,w,x.fi) { dp[i]=max(dp[i],dp[i-x.fi]+x.se); } } ll ans=0; forr(i,0,w) ans=max(ans,dp[i]); cout<<ans; } int main() { ios::sync_with_stdio(false); cin.tie(0); // freopen(file".inp","r",stdin); freopen(file".out","w",stdout); int test=1; // cin>>test; while (test--) { solve(); } return 0; }