#include<bits/stdc++.h>
#define ll long long
#define nl "\n"
#define all(v) v.begin(),v.end()
#define baraa ios_base::sync_with_stdio(false);cin.tie(NULL);
using namespace std;
int main() {
baraa
ll s, n, m = 2e3 + 5;
cin >> s >> n;
vector<vector<ll>>w(m);
vector<array<ll, 3>>a(n);
for (ll i = 0; i < n; i++)
for(ll j = 0; j < 3; j++)
cin >> a[i][j];
sort(all(a), greater());
for (ll i = 0; i < n; i++)
while(w[a[i][1]].size() < m and a[i][2]--)
w[a[i][1]].push_back(a[i][0]);
vector<vector<ll>>dp(m, vector<ll>(m, -1));
function<ll(ll, ll)>solve = [&](ll i, ll rem) -> ll{
if (rem < 0)return -1e16;
if (i == m)return 0;
if (dp[i][rem] != -1)return dp[i][rem];
ll ret = solve(i + 1, rem), prf = 0, cost = 0;
for (ll j = 0; j < w[i].size() and rem - cost + i >= 0; j++){
prf += w[i][j];
cost += i;
ret = max(ret, solve(i + 1, rem - cost) + prf);
}
return dp[i][rem] = ret;
};
cout << solve(0, s);
return 0;
}
