#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=1e6+1;
const ll mo=1e9+7;
const ll inf=1e15;
struct kool
{
ll v,w,k;
};
bool cmp(kool x,kool y)
{
return ( (x.w<y.w) || (x.w==y.w && x.v>y.v) || (x.w==y.w && x.v==y.v && x.k>y.k) );
}
ll cntk[maxN+1];
ll dp[maxN+1];
map <ll,map<ll,ll> > mp,findkey;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
ll n,s;
cin>>s>>n;
kool a[n+1];
ll cntcnt=1;
for(ll i=1;i<=n;i++)
{
ll lmao1,lmao2,lmao3;
cin>>lmao1>>lmao2>>lmao3;
if(mp[lmao1][lmao2]==0)
{
a[i].v=lmao1;
a[i].w=lmao2;
a[i].k=lmao3;
findkey[lmao1][lmao2]=i;
mp[lmao1][lmao2]+=a[i].k;
}
else
{
mp[lmao1][lmao2]+=lmao3;
a[findkey[lmao1][lmao2]].k+=lmao3;
cntcnt++;
a[i].v=cntcnt;
a[i].w=inf;
a[i].k=-inf;
}
// cin>>a[i].v>>a[i].w>>a[i].k;
}
sort(a+1,a+n+1,cmp);
vector<pii> items;
for(ll i=1;i<=n;i++)
{
ll v=a[i].v;
ll w=a[i].w;
ll k=a[i].k;
if(w==inf)
continue;
ll temp=s/w;
if(cntk[w]<temp)
{
ll lmao=cntk[w];
lmao+=k;
if(lmao<=temp)
{
cntk[w]=lmao;
while(k--)
items.push_back({v,w});
}
else
{
lmao=temp-cntk[w];
cntk[w]=temp;
while(lmao--)
items.push_back({v,w});
}
}
}
// for(ll i=1;i<=n;i++)
// cout<<a[i].w<<" "<<a[i].v<<" "<<a[i].k<<endl;
// cout<<endl;
// for(auto i:items)
// cout<<i.fi<<" "<<i.se<<endl;
for(auto i:items)
{
for(ll j=s;j>=i.se;j--)
dp[j]=max(dp[j],dp[j-i.se]+i.fi);
// for(ll j=1;j<=s;j++)
// cout<<dp[j]<<" ";
// cout<<endl;
}
ll ans=-inf;
for(ll i=0;i<=s;i++)
ans=max(ans,dp[i]);
cout<<ans;
return 0;
}
