/**
* بسم الله الرحمن الرحيم *
﴾ رَبِّ اشْرَحْ لِي صَدْرِي * وَيَسِّرْ لِي أَمْرِي * وَاحْلُلْ عُقْدَةً مِّن لِّسَانِي * يَفْقَهُوا قَوْلِي ﴿
*/
/// author : "ASGA"
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
signed main(){
ios_base::sync_with_stdio(0);cin.tie(0);
ll s,n;cin>>s>>n;
vector<ll>d(s+1,0);
while(n--){
ll v,w,k;cin>>v>>w>>k;
vector<multiset<ll>>a(w);
vector<ll>vv(s+1,0);
for(ll i=0;i<=s;i++){
vv[i]=v*((s-i+w)/w);
}
for(ll i=s;i>=0;i--){
ll sz=a[i%w].size();
if(sz<k)a[i%w].insert(d[i]+vv[i]);
}
vector<ll>cnt(w,0);
for(ll i=s;i>=w;i--){
a[i%w].erase(a[i%w].find(d[i]+vv[i]));cnt[i%w]+=v;
if(i>=w*k)a[i%w].insert(d[i-w*k]+vv[i-w*k]);
ll val=*a[i%w].rbegin()-cnt[i%w];
d[i]=max(d[i],val);
}
}
cout<<*max_element(d.begin(),d.end());
return 0;
}
