// Source: https://usaco.guide/general/io
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,a,b) for(int i=a; i<=b; i++)
#define fs first
#define sc second
#define pb push_back
const int N=1e6+3;
const int R=2002;
int a[N],v[N],w[N],k[N],dp[N];
vector<pair<int,int>> vec[N],vec1;
signed main(){
int n,s; cin>>s>>n;
rep(i,1,n){cin>>v[i]>>w[i]>>k[i]; vec[w[i]].pb({v[i],k[i]});}
rep(i,1,s){
sort(vec[i].begin(),vec[i].end());
reverse(vec[i].begin(),vec[i].end());
for(int j=0; j<vec[i].size(); j++){
int sum=0,pow=1;
int k1=vec[i][j].sc;
int v1=vec[i][j].fs;
while(sum<s and k1){
sum+=pow*i;
k1-=pow;
if(k1<0) break;
vec1.pb({pow*i,pow*v1});
pow++;
}
}
for(int i1=0; i1<vec1.size(); i1++){
for(int j1=s; j1>=vec1[i1].fs; j1--){
dp[j1]=max(dp[j1],dp[j1-vec1[i1].fs]+vec1[i1].sc);
}
}
vec1.clear();
}
// for(auto x:vec){
// cout<<x.fs<<" "<<x.sc<<" "<<endl;
// }
// for(int kl=1; kl<=n; kl++){
// for(int i=0; i<vec[kl].size(); i++){
// for(int j=s; j>=vec[kl][i].sc; j--){
// dp[j]=max(dp[j-vec[kl][i].sc]+vec[kl][i].fs,dp[j]);
// }
// }
// }
cout<<dp[s]<<endl;
}
