#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
const int N=1e5+100;
const int S=2001;
const ll inf=1e18;
int w[N],v[N],k[N];
ll dp[N],ad[N];
ll vec[S][S];
deque<int> cur[N];
int32_t main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int s,n;
cin>>s>>n;
for(int i=0;i<n;i++)
{
cin>>v[i]>>w[i]>>k[i];
k[i]=min(2000ll,k[i]);
}
// dp[i][s] = max value
// dp[i][s] = dp[i-1][s] take no elements
// dp[i][s] = dp[i-1][s-w[i]]+v[i] 1 ele
// dp[i][s] = max(dp[i-1][s-k*w[i]]+v[i]*k)
for(int i=0;i<n;i++)
{
// dp[x] = max(dp[x-w[i]])
for(int idp=0;idp<=s;idp++)
{
if(idp<w[i])
{
// [0,s]
// how many with mod w[i] =idp
// idp+k*w[i] <=s
// k <= (s-idp)/w[i]
// int tlp=(s-idp)/w[i]; // tlp>=0
// vec[idp].clear();
// vec[idp].resize(tlp+1);
cur[idp].clear();
// cur[idp].reserve(k[i]);
ad[idp]=0;
}
int x=idp%w[i],j=idp/w[i];
vec[x][j]=dp[idp];
// ll ad=0;
// for(int j=vec[x].size()-1;j<vec[x].size();j++)
{
ad[x]+=v[i];
// cur[0]>= cur[1]>=cur[2]
while(cur[x].front()<j-k[i])
cur[x].pop_front();
vec[x][j]-=ad[x];
while(cur[x].size()>0 and vec[x][cur[x].back()]<vec[x][j])
cur[x].pop_back();
cur[x].push_back(j);
// cur[x].insert(vec[x][j]-ad[x]);
if(cur[x].size()>0)
dp[idp]=vec[x][cur[x].front()]+ad[x];
}
}
}
ll mx=0;
for(int i=0;i<=s;i++)mx=max(mx,dp[i]);
cout<<mx<<endl;
}
