//UPDATERA ARRAY STORLEKEN!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF=1e15;
const ll MAXS=2006;//UPDATERA ARRAY STORLEKEN!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! 1e7
ll n,ans,s,k,v,w,dp[MAXS];
vector<ll> group[MAXS];
int main(){//多重背包模板
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin>>s>>n;
for(int i=1;i<=n;i++){
cin>>v>>w>>k;
ll now=1;
while(k>=now){
k-=now;
if(w*now>s){
now*=2;
continue;//k big, many unnecessary
}
group[w*now].push_back(v*now);
now*=2;
}
if(k){
if(w*k>s) continue;
group[w*k].push_back(v*k);
}
}
for(int i=1;i<=s;i++) sort(group[i].begin(),group[i].end(),greater<ll>());
for(int i=1;i<=s;i++){
for(int j=0;j<group[i].size();j++){
for(int k=s;k>=i;k--){
dp[k]=max(dp[k],dp[k-i]+group[i][j]);
ans=max(ans,dp[k]);
}
}
}
cout<<ans<<'\n';
}
