#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N(1e5+9),K(2e3+9);
int n,k;
int dp[K][K];
vector<pair<int,int>> vp[K];
int32_t main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);
cin >> k >> n;
memset(dp,-1,sizeof(dp));
for(int i=0;i<n;i++){
int a,b,c;cin >> a >> b >> c;
if(a<=k && c>0)vp[b].emplace_back(a,c);
}
int now=1;
dp[0][0]=0;
for(int w=1;w<=k;w++){
if(vp[w].empty())continue;
sort(vp[w].begin(),vp[w].end(),greater<pair<int,int>>());
for(int i=0;i<=k;i++){
dp[now][i]=dp[now-1][i];
int use=0;
int sum=0;
int at=0;
int pos=0;
while((use+1)*w<=i && at<vp[w].size()){
use++;
sum += vp[w][at].first;
if(dp[now-1][i-(use*w)]!=-1){
dp[now][i]=max(dp[now][i],dp[now-1][i-(use*w)]+sum);
}
pos++;
if(pos==vp[w][at].second){
pos=0;
at++;
}
}
}
now++;
}
int ans=0;
for(int i=0;i<=k;i++){
ans=max(ans,dp[now-1][i]);
}
cout << ans << "\n";
return 0;
}
