#include<bits/stdc++.h>
using namespace std;
#define int long long
struct st{
int w;
int v;
int k;
};
signed main()
{
int s,n;
cin>>s>>n;
vector<int> v;
map<int,int> mp;
vector<priority_queue<pair<int,int>>> pq(2000);
for(int i=0; i<n; i++)
{
int w,vl,k;
cin>>vl>>w>>k;
if(w>2000) continue;
k=min(k, s/w);
if(!mp[w]) v.push_back(w);
// k=min(k, (s/w)-mp[w]);
// if(k==0) continue;
pq[w].push({vl,k});
// mp[w]+=k;
}
sort(v.begin(), v.end());
map<int, map<int,int>> cost;
vector<int> wt, val;
for(int i: v)
{
int ss=s/i;
while(!pq[i].empty())
{
for(int j=0; j<min(ss,pq[i].top().second); j++)
{
wt.push_back(i);
val.push_back(pq[i].top().first);
}
ss-=min(ss,pq[i].top().second);
pq[i].pop();
}
}
vector<vector<int>> dp(wt.size()+1, vector<int> (s+1, 0));
// for(int i: wt) cout<<i<<" ";
// cout<<endl;
// for(int i: val) cout<<i<<" ";
// cout<<endl;
for(int i=1; i<=wt.size(); i++)
{
for(int j=1; j<=s; j++)
{
if(j<wt[i-1])
{
dp[i][j]=dp[i-1][j];
}
else
{
dp[i][j]=dp[i-1][j];
if(j-wt[i-1]>=0)
dp[i][j]=max(dp[i][j], dp[i-1][j-wt[i-1]]+val[i-1]);
}
}
}
int ans=0;
// for(auto i: dp)
// {
// for(auto j: i)
// cout<<j<<" ";
// cout<<endl;
// }
for(int i=0; i<dp.size(); i++)
{
for(int j=0; j<dp[i].size(); j++)
{
ans=max(ans, dp[i][j]);
}
}
cout<<ans<<endl;
}
