#include<bits/stdc++.h>
#define ll long long
using namespace std;
// void solve(int test){
// }
int main()
{
// ios::sync_with_stdio(0);
// cin.tie(0);
// cout.tie(0);
int W,n;
cin>>W>>n;
int dp[2][W+1]={};
int w,v,c;
for(int i=1;i<=n;i++){
cin>>v>>w>>c;
bool c1=i&1;
bool c2=!c1;
for(int r=0;r<w;r++){
deque<pair<int, int>>dq;
for(int q = 0 , cur= r, sum=0; cur <= W; q++,cur+=w,sum+=v){
int cur_val = dp[c2] [cur] - sum;
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] [cur] = dq.front().first + sum ;
}
}
}
int ans=0;
bool p=n&1;
for(int i=0;i<=W;i++)ans=max(ans,dp[p][i]);
cout<<ans;
// int t=1;
// // cin>>t;
// for(int i=1;i<=t;i++)
// solve(i);
}
