#include <bits/stdc++.h>
using namespace std;
#define ll unsigned long long
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
ll n, k, a, b, c;
cin>>k>>n;
vector <pair<ll, ll> > vect[k+1];
ll dp[k+1];
for (int j=0; j<=k; ++j){
dp[j] = 0;
}
for (int i=1; i<=n; ++i){
cin>>a>>b>>c;
vect[b].push_back(make_pair(a, c));
}
for (int i=1; i<=k; ++i){
sort(vect[i].begin(), vect[i].end(), greater<pair<ll, ll> >());
int index = 0;
for (int j=0; j<k/i; ++j){
if (index>=vect[i].size())break;
for (int l=k; l>=i; --l){
dp[l] = max(dp[l], dp[l-i]+vect[i][index].first);
}
--vect[i][index].second;
if (vect[i][index].second==0)++index;
}
}
cout<<dp[k];
}
