#include <bits/stdc++.h> using namespace std; #define ll long long #define FASTIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int main(){ FASTIO int S,N; cin>>S>>N; vector<ll> dp(S+1,0); for(int i=0;i<N;i++){ ll V,W,K; cin>>V>>W>>K; ll cnt=1; while(K>0){ ll take=min(cnt,K); ll ww=W*take, vv=V*take; for(int j=S;j>=ww;j--) dp[j]=max(dp[j],dp[j-ww]+vv); K-=take; cnt*=2; } } cout<<dp[S]; }