#include<bits/stdc++.h> #define int long long using namespace std; const int N=55; int n,v,c[N],w[N],t[N],f[N][300]; signed main(){ cin>>v>>n; for(int i=1;i<=n;i++){ cin>>c[i]>>w[i]>>t[i]; } for(int i=1;i<=n;i++){ for(int j=0;j<=v;j++){ f[i][j]=f[i-1][j]; if(t[i]!=0){ for(int k=1;k<=j/c[i]&&k<=t[i];k++){ if(j-c[i]*k>=0)f[i][j]=max(f[i][j],f[i-1][j-c[i]*k]+w[i]*k); } } else if(j-c[i]>=0)f[i][j]=max(f[i][j],w[i]+f[i][j-c[i]]); } } cout<<f[n][v]; return 0; }