#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
const int N=1e5+100;
const ll inf=1e18;
int w[N],v[N],k[N];
ll dp[N];
vector<ll> vec[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 x=0;x<=s;x++)
{
vec[x%w[i]].push_back(dp[x]);
}
for(int x=0;x<w[i];x++)
{
multiset<ll> cur={-inf};
ll ad=0;
for(int j=0;j<vec[x].size();j++)
{
ad+=v[i]; // add v[i] to each element in cur
if(j-1-k[i]>=0)
{
cur.erase(cur.find(vec[x][j-1-k[i]]+(k[i]+1)*v[i]-ad));
}
cur.insert(vec[x][j]-ad);
ll idp=w[i]*j+x;
dp[idp]=max((*rbegin(cur))+ad,0ll);
// vec[x][j-k]+(k+1)v -ad
//
// vec[x][j] vec[x][j-1]+v vec[x][j-2]+2v .. vec[x][j-k]+kv
// vec[x][j+1] vec[x][j]+v vec[x][j-1]+2v .. vec[x][j+1-l]+kv vec[x][j-k]+(k+1)v
}
vec[x].clear();
}
}
ll mx=0;
for(int i=0;i<=s;i++)mx=max(mx,dp[i]);
cout<<mx<<endl;
}
