#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll MOD = 1000000007;
int main()
{
// #ifndef ONLINE_JUDGE
// freopen("input.in", "r", stdin);
// freopen("output.out", "w", stdout);
// #endif
ll n,s;
cin>>s>>n;
vector<ll> dp(s+1,0);
dp[0]=1;
map<ll,vector<pair<ll,ll>>> store;
ll v,w,k;
for (ll i = 0; i < n; i++)
{
cin>>v>>w>>k;
store[w].push_back({v,k});
}
for (auto st:store)
{
sort(st.second.begin(),st.second.end());
reverse(st.second.begin(),st.second.end());
}
ll ind=0,x=0;
for (ll i = 1; i <= s; i++)
{
ind=0;
if(store[i].size()==0)continue;
for (ll j = 0; j <= (s/i); j++)
{
if(store[i][ind].second){
store[i][ind].second--;
x=store[i][ind].first;
}else{
ind++;
if(ind<(ll)store[i].size()){
store[i][ind].second--;
x=store[i][ind].first;
}
}
if(ind>=(ll)store[i].size())break;
ind++;
for (ll k = s; k >= 0; k--)
{
if(dp[k]&&i+k<=s)dp[i+k]=max(dp[i+k],dp[k]+x);
}
if(ind>=(ll)store[i].size())break;
}
}
ll ans=0;
for (ll i = 0; i <= s; i++)
{
ans=max(ans,dp[i]);
}
cout<<ans-1<<endl;
return 0;
}
