#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MAXN (1000005)
int main() {
ios_base::sync_with_stdio(false);cin.tie(0);
ll S,N;
cin>>S>>N;
ll V[N], W[N], K[N];
for(ll i = 0;i < N;i++){
cin>>V[i]>>W[i]>>K[i];
K[i] = min(K[i],S);
}
vector<ll> weight[S + 1];
for(ll i = 0;i < N;i++){
ll k = K[i];
ll pwrof2 = 1;
while(k >= pwrof2){
if(pwrof2 * W[i] > S) break;
weight[pwrof2 * W[i]].push_back(pwrof2 * V[i]);
k -= pwrof2;
pwrof2 *= 2;
}
if(k >= 1){
if(k * W[i] > S) continue;
weight[k * W[i]].push_back(k * V[i]);
k = 0;
}
}
for(ll i = 0;i <= S;i++){
sort(weight[i].begin(),weight[i].end(),greater<ll>());
}
vector<pair<ll,ll> > items;
for(ll w = 1;w <= S;w++){
ll needed = S / w;
//we only need to consider the top (S / w) elements sorted by decreasing value
for(ll i = 0;i < min(ll(weight[w].size()),needed);i++){
items.push_back({weight[w][i],w});
}
}
N = items.size();
ll dp[S + 1];
memset(dp,0,sizeof(dp));
for(ll i = 0;i < N;i++){
ll v = items[i].first;
ll w = items[i].second;
for(ll j = S - w;j >= 0;j--){
dp[j + w] = max(dp[j + w],dp[j] + v);
}
}
ll maximum = 0;
for(ll i = 0;i <= S;i++){
maximum = max(maximum,dp[i]);
}
cout<<maximum<<'\n';
}
