#include <bits/stdc++.h>
typedef long long ll;
#define endl "\n"
#define pii pair<ll,ll>
#define fi first
#define se second
using namespace std;
const ll maxN=2001;
struct items
{
ll w,v,cnt;
};
vector<items> item;
bool cmp(items a,items b)
{
return a.v>b.v;
}
ll s,n;
ll lef[maxN+1];
ll dp[maxN+1];
ll vi[maxN+1];
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
//freopen(".inp","r",stdin);
//freopen(".out","w",stdout);
cin>>s>>n;
for(ll i=1;i<=n;i++)
{
ll w,v,cnt;
cin>>v>>w>>cnt;
item.push_back({w,v,cnt});
}
sort(item.begin(),item.end(),cmp);
for(ll i=1;i<=s;i++)
lef[i]=s/i;
vector<items> kul;
for(auto i:item)
{
if(lef[i.w]==0)
continue;
ll ok=min(lef[i.w],i.cnt);
lef[i.w]-=ok;
// cout<<"aa "<<i.w<<" "<<i.v<<endl;
while(ok--)
kul.push_back({i.w,i.v,1});
}
vi[0]=1;
for(auto i:kul)
{
// cout<<i.w<<" "<<i.v<<" ________________"<<endl;
for(ll j=maxN;j>=i.w;j--)
if(vi[j-i.w]==1)
{
// cout<<j<<" "<<i.w<<" "<<i.v<<" ";
dp[j]=max(dp[j],dp[j-i.w]+i.v);
// cout<<dp[j]<<endl;
vi[j]=1;
}
}
ll ans=0;
for(ll i=1;i<=s;i++)
ans=max(ans,dp[i]);
cout<<ans;
return 0;
}
