#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,c;
vector<int> a, dp;
vector<vector<int>> pref, ct;
vector<vector<array<int, 2>>> p;
int find(const int w, const int k){
//cout<<'a'<<endl;
const auto m=ct[w].size();
auto idx=lower_bound(ct[w].begin(), ct[w].end(), k)-ct[w].begin();
if (ct[w][idx]>k) --idx;
assert(idx>=0);
//cout<<'c'<<endl;
int sm=pref[w][idx];
//cout<<'d'<<endl;
//cout<<w<<' '<<idx+1<<' '<<m<<' '<<p[w][idx+1][0]<<' '<<k<<endl;
//for (const auto [a, b]:p[w]) cout<<a<<' '<<b<<endl;
sm+=p[w][idx][0]*(k-ct[w][idx]);
//cout<<'b'<<endl;
return sm;
}
signed main(){
ios_base::sync_with_stdio(0);
cout.tie(0);
cin.tie(0);
cin>>c>>n;
a.assign(c+1, 0);
p.assign(c+1, {{0,0}});
pref.assign(c+1, {0});
ct.assign(c+1, {0});
dp.assign(c+1, 0);
for (int i=0; i<n; i++){
int v, w, k, t;
cin>>v>>w>>k;
p[w].push_back({v, k});
}
for (int w=1; w<=c; w++){
sort(p[w].rbegin(), p[w].rend());
const auto t=c/w;
for (const auto [v, k]:p[w]){
pref[w].push_back(pref[w].back()+min(t-a[w], k)*v);
a[w]=min(t, a[w]+k);
ct[w].push_back(a[w]);
}
}
for (int i=1; i<=c; i++){
for (int r=0; r<i; r++){
deque<array<int, 2>> q;
for (int j=r; j<=c; j+=i){
if (!q.empty() && j-q.front()[0]>a[i]*i) q.pop_front();
while (!q.empty() && q.back()[1]+find(i, (j-q.back()[0])/i)<=dp[j]) q.pop_back();
q.push_back({j, dp[j]});
const auto k=(j-q.front()[0])/i;
dp[j]=max(dp[j], q.front()[1]+find(i, k));
}
}
}
cout<<dp.back()<<'\n';
}
