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