#include<bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define int long long
#define ordered_set tree<pair<int,int>, null_type,less<pair<int,int>>, rb_tree_tag,tree_order_statistics_node_update>
#define eb emplace_back
#define S second
#define dbg(v) cerr << #v << " = " << v << "\n"
#define F first
#define fall(i,a,n) for(int i=a;i<=n;i++)
#define rfall(i,a,n) for(int i=a;i>=n;i--)
#define pb push_back
#define all(x) x.begin(),x.end()
#define lsb(x) (x & -x)
#define sz(x) (int)x.size()
const int MAXN=2e3+10;
const int MAXL=1e5+10;
const int inf=1e18;
const int MOD=1e9+7;
typedef pair<int,int> pii;
typedef tuple<int,int,int>trio;
typedef tuple<int,int,int,int> squad;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int n,k,dp[MAXN],tira[MAXN],aux[MAXN];
multiset<pii> st[MAXN];
vector<int> v[MAXN];
int32_t main(){
std::ios_base::sync_with_stdio(false);
cin.tie(NULL);
//freopen("odometer.in","r",stdin);
//freopen("odometer.out","w",stdout);
cin>>k>>n;
fall(i,1,k) dp[i]=-inf;
int ans=0;
fall(i,1,n){
int val,p,q; cin>>val>>p>>q;
st[p].insert({-val,q});
}
fall(i,1,k){
while(st[i].size()>0){
auto it=st[i].begin(); st[i].erase(it);
auto [x,u]=*it;
for(int j=1;j<=u && sz(v[i])<=k;j++) v[i].pb(-x);
if(v[i].size()==k) break;
}
}
fall(i,1,k){
rfall(j,k,1){
int r=1,ans=0;
while(r<=sz(v[i]) && j-r*i>=0){
ans+=v[i][r-1];
dp[j]=max(dp[j],dp[j-r*i]+ans);
r++;
}
}
}
int x=0;
fall(i,0,k) x=max(x,dp[i]);
cout<<x<<"\n";
}
