#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
signed main(){
ios_base::sync_with_stdio(0);
cout.tie(0);
cin.tie(0);
int c,n;
cin>>c>>n;
//cout<<'a'<<endl;
vector<int> a(c+1,0);
//cout<<'b'<<endl;
vector<vector<int>> pref(c+1, vector<int>(1, 0));
//cout<<'c'<<endl;
for (int i=0; i<n; i++){
int v, w, k;
cin>>v>>w>>k;
if ((a[w]+k)*w>c) {
const auto t=a[w];
for (int j=t+1; j<=t+k; j++){
if (j*w>c) break;
pref[w].push_back(pref[w].back()+v);
++a[w];
}
} else {
for (int j=a[w]+1; j<=a[w]+k; j++){
pref[w].push_back(pref[w].back()+v);
}
a[w]+=k;
}
}
vector<int> dp(c+1, 0);
for (int i=1; i<=c; i++){
if (!a[i]) continue;
for (int j=0; j<i; j++){
deque<pair<int, int>> q;
for (int k=j; k<=c; k+=i){
if (!q.empty() && k-q.front().first>i*a[i]) q.pop_front();
while (!q.empty() && q.back().second+pref[i][(k-q.back().first)/i]<=dp[k]) q.pop_back();
q.emplace_back(k, dp[k]);
const auto t=(k-q.front().first)/i;
dp[k]=max(dp[k], q.front().second+pref[i][t]);
}
}
}
cout<<dp.back()<<'\n';
}
