// Source: https://usaco.guide/general/io
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,a,b) for(int i=a; i<=b; i++)
#define fs first
#define sc second
#define pb push_back
const int N=2*1e5+3;
const int R=2002;
int a[N],v[N],w[N],k[N],dp[N];
vector<pair<int,int>> vec[N];
signed main(){
int n,s; cin>>s>>n;
rep(i,1,n){cin>>v[i]>>w[i]>>k[i]; k[i]=min(k[i],R);}
rep(i,1,n){
int pow=1;
int k2=k[i];
while(pow<=k2){
k2-=pow;
pair<int,int> pr;
pr.fs=v[i]*pow;
pr.sc=w[i]*pow;
vec[i].pb(pr);
pow++;
if(pow>k2 and k2!=0){
pr.fs=v[i]*k2;
pr.sc=w[i]*k2;
vec[i].pb(pr);
}
}
}
// for(auto x:vec){
// cout<<x.fs<<" "<<x.sc<<" "<<endl;
// }
for(int kl=1; kl<=n; kl++){
for(int i=0; i<vec[kl].size(); i++){
for(int j=s; j>=vec[kl][i].sc; j--){
dp[j]=max(dp[j-vec[kl][i].sc]+vec[kl][i].fs,dp[j]);
}
}
}
cout<<dp[s]<<endl;
}
