#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll lim = 2222;
ll n,x;
map<ll, vector<pair<ll,ll>>> g;
ll dp[lim];
void init()
{
cin.tie(0);
cout.tie(0);
ios_base::sync_with_stdio(0);
}
bool cmp(pair<ll,ll> x, pair<ll,ll> y)
{
if(x.first != y.first) return x.first > y.first;
if(x.second != y.second) return x.second > y.second;
return 1;
}
int main()
{
init();
cin >> x >> n;
for(ll i = 0; i < n; i++)
{
ll u;
pair<ll,ll> v;
cin >> v.first >> u >> v.second;
if(v.second > x) v.second = n;
g[u].push_back(v);
}
for(auto &[w,v]:g)
{
sort(v.begin(), v.end(), cmp);
vector<pair<ll,ll>> a;
ll cnt = 0;
for(ll i = 0; i < v.size(); i++)
{
cnt += v[i].second;
if(cnt * w > x)
{
v = a;
break;
}
else a.push_back(v[i]) ;
}
}
for(auto &[w,v]:g)
{
for(ll i = 0; i < v.size(); i++)
{
for(ll k = 1; k <= v[i].second; k++)
{
for(ll j = x; j >= 0; j--)
{
if(j + w > x) continue;
if(dp[j]) dp[j + w] = max(dp[j + w], dp[j] + v[i].first);
if(j == 0)
dp[w] = max(dp[w], v[i].first);
}
}
}
}
ll ans = 0;
for(ll i = 0; i <= x; i++) if(dp[i]) ans = max(ans, dp[i]);
cout << ans;
}
