#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;
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});
k-=c;
c=(c<<1);
}
if(k>0){
objs.push_back({v*k,w*k});
}
}
ll dp[s+1];
// dp[0]=0;
forn(i,s+1){
dp[i]=0;
}
forn(j,objs.size()){
auto [v,w]=objs[j];
if(w>s)continue;
for(ll i=s-w;i>=0;i--){
dp[i+w]=max(dp[i+w],dp[i]+v);
}
}
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;
}
