#include<bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); int S,N; cin>>S>>N; long long dp[2001]; for(int i=0;i<=S;i++) { dp[i]=0; } for(int i=1;i<=N;i++) { long long V,W,K; cin>>V>>W>>K; long long c=1; while(K>0) { long long t=min(c,K); long long wt=t*W; long long val=t*V; if(wt<=S) { for(int s=S;s>=wt;s--) { dp[s]=max(dp[s],dp[s-wt]+val); } } K-=t; c<<=1; } } long long r=0; for(int i=0;i<=S;i++) { r=max(r,dp[i]); } cout<<r; return 0; }