#include<bits/stdc++.h>
using ll = long long;
using ld = long double;
using namespace std;
#define endl "\n";
#define ff first
#define ss second
#define forn(i,n) for(int i=0;i<n;i++)
#define dbgv(v) cout<<#v<<" "<<v<<endl
#define dbga(a,n) forn(i,n-1) {cout<<a[i]<<' ';} cout<<a[n-1]<<'\n';
void solve(){
ll s,n;
cin>>s>>n;
// vector<pair<ll,ll>> objs;
vector<priority_queue<ll>> objs(s);
forn(i,n){
ll v,w,k;
cin>>v>>w>>k;
ll c=1;
while(k>=c && k>0 && c>0 && c*w<=s){
// objs.push_back({v*c,c*w});
objs[c*w-1].push(v*c);
k-=c;
c=(c<<1);
}
if(k>0 && w*k<=s){
objs[w*k-1].push(v*k);
}
}
ll dp[s+1];
// dp[0]=0;
forn(i,s+1){
dp[i]=0;
}
forn(j,objs.size()){
// auto [v,w]=objs[j];
ll si=objs[j].size();
for(int k=0;k<min(s/(j+1)+1,si);k++){
ll v=objs[j].top();
objs[j].pop();
ll w=j+1;
for(ll i=s-w;i>=0;i--){
dp[i+w]=max(dp[i+w],dp[i]+v);
}
}
// if(w>s)continue;
}
cout<<dp[s]<<endl;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int T = 1;
// cin >> T;
while(T--){
solve();
}
return 0;
}
