#include <bits/stdc++.h>
using namespace std;
int main()
{
int s,n;
cin>>s>>n;
vector<int>v(n);
vector<int>w(n);
vector<int>k(n);
vector<long long>dp(s+1,0);
for(int i=0;i<n;i++)cin>>v[i]>>w[i]>>k[i];
vector<vector<pair<int,int>>>p(s+1);
vector<pair<int,int>>a;
for(int i=0;i<n;i++)
{
p[w[i]].push_back(make_pair(v[i],k[i]));
}
for(int i=1;i<=s;i++)
{
sort(p[i].begin(),p[i].end());
}
for(int i=1;i<=s;i++)
{
int uk=0;
int j=0;
while(j<p[i].size())
{
int k=0;
while(k<p[i][j].second)
{
a.push_back(make_pair(p[i][j].first,i));
k++;
uk++;
if(uk>s/i)break;
}
if(uk>s/i)break;
j++;
}
}
for(int i=0;i<a.size();i++)
{
vector<long long>dppom=dp;
for(int j=a[i].second;j<=s;j++)
{
dppom[j]=max(dp[j],dp[j-a[i].second]+a[i].first);
}
dp=dppom;
}
cout<<dp[s]<<endl;
}
