#include <bits/stdc++.h>
using namespace std;
#define ll long long
// #define int ll
const int N=1e5+100;
const int S=2005;
const ll inf=1e18;
int w[N],v[N],k[N];
ll dp[S];//,ad[S];
// int l[S],r[S];
// ll vec[S][S];
// int cur[S][S];
ll pre[S][S];
vector<pair<ll,int>> pq[S];
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((2000)/w[i],k[i]);
pq[w[i]].push_back({v[i],k[i]});
}
for(int wi=1;wi<=2000;wi++) // current weight begin processed
{
// int sz=pq[wi].size();
// if(sz>0)
// {
// cout<<"For "<<wi<<' '<<sz<<endl;
// }
sort(begin(pq[wi]),end(pq[wi]));
for(int i=1;i<=(2000/wi) and pq[wi].size()>0;i++)
{
int cur=pq[wi].back().first;
pq[wi].back().second--;
if(pq[wi].back().second==0)
{
pq[wi].pop_back();
}
// cout<<wi<<' '<<cur<<endl;
for(int i=2000;i>=wi;i--)
{
dp[i]=max(dp[i-wi]+cur,dp[i]);
}
}
}
// for(int i=0;i<n;i++)
// {
// for(int idp=0;idp<=s;idp++)
// {
// if(idp<w[i])
// {
// l[idp]=r[idp]=0;
// ad[idp]=0;
// }
// int x=idp%w[i],j=idp/w[i];
// vec[x][j]=dp[idp];
// {
// ad[x]+=v[i];
// while(l[x]<r[x] and cur[x][l[x]]<j-k[i])
// l[x]++;
// vec[x][j]-=ad[x];
// while(l[x]<r[x] and vec[x][cur[x][r[x]-1]]<=vec[x][j])
// r[x]--;
// cur[x][r[x]]=j;
// r[x]++;
// if(l[x]<r[x])
// dp[idp]=vec[x][cur[x][l[x]]]+ad[x];
// }
// }
// }
ll mx=0;
for(int i=0;i<=s;i++)mx=max(mx,dp[i]);
cout<<mx;
}
