#include<bits/stdc++.h>
#define ll long long
using namespace std;
// void SolveBoundedKnapsack(ll &dp[] ,int w, int v, int c, int W){
// ll next_dp[W] = dp;
// for(int r=0;r<w;r++){
// deque<pair<ll, int>>dq;
// for(int q = 0; q*w+r <= W; q++){
// ll cur_val = dp[q*w+r] - q*v;
// while(!dq.empty() && dq.back().first <= cur_val)dq.pop_back();
// dq.push_back({cur_val,q});
// if(dq.front().second < q-c)dq.pop_front();
// next_dp[q*w+r] = dq.front().first + q*v ;
// }
// }
// dp = next_dp;
// }
void solve(int test){
int W,n;
cin>>W>>n;
ll dp[2][W+1]={};
#define c1 (bool)(i&1)
#define c2 (bool)(!c1)
int w,v,c;
for(int i=1;i<=n;i++){
cin>>v>>w>>c;
for(int r=0;r<w;r++){
deque<pair<ll, int>>dq;
for(int q = 0; q*w+r <= W; q++){
ll cur_val = dp[c2] [q*w+r] - q*v;
while(!dq.empty() && dq.back().first <= cur_val)dq.pop_back();
dq.push_back({cur_val,q});
if(dq.front().second < q-c)dq.pop_front();
dp[c1] [q*w+r] = dq.front().first + q*v ;
}
}
}
ll ans=0;
for(auto x:dp[n&1])ans=max(ans,x);
cout<<ans;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t=1;
// cin>>t;
for(int i=1;i<=t;i++)
solve(i);
}
