/*
*
* ^v^
*
*/
#include <iostream>
#include <string>
#include <cmath>
#include <vector>
#include <iomanip>
#include <map>
#include <algorithm>
#include <set>
#include <queue>
#include <climits>
#include <cstdlib>
#include <chrono>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
using namespace std;
// #define ordered_set tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update>
#define iamtefu ios_base::sync_with_stdio(false); cin.tie(0);
#define ll long long int
#define ld long double
#define fl(i,a,n) for (ll i(a); i<n; i++)
#define rfl(i,a,n) for (ll i(n-1); i>=a; i--)
#define print(a) for (auto x:a){cout<<x<<" ";} cout<<"\n";
#define tt int tt; cin>>tt; for(;tt--;)
template <typename T1, typename T2>
decltype(auto) max(T1 a, T2 b){return (a>b?a:b);}
template <typename T1, typename T2>
decltype(auto) min(T1 a, T2 b){return (a<b?a:b);}
ll gcd(ll a, ll b){
if (b==0){
return a;
}
return gcd(b, a%b);
}
ll pw(ll a, ll b, ll m){
ll res=1;
a%=m;
while (b){
if (b&1){
res=(res*a)%m;
}
a=(a*a)%m;
b>>=1;
}
return res;
}
void scn(){
ll n, s; cin>>s>>n;
vector <vector <vector <ll>>> huh(s+1);
fl(i,0,n){
ll v, w, k; cin>>v>>w>>k;
huh[w].push_back({v, k});
}
for (auto &x:huh){
sort(x.begin(), x.end());
}
vector <vector <ll>> eheh;
fl(i,1,s+1){
ll sz = (s+i-1)/i;
for (auto x:huh[i]){
ll jk = min(sz, x[1]);
while (jk){
jk--;
eheh.push_back({x[0], i});
}
sz-=(min(sz, x[1]));
}
}
vector <vector<ll>> dp(eheh.size()+1, vector <ll>(s+1));
fl(i,1,eheh.size()+1){
fl(j,0,s+1){
dp[i][j]=dp[i-1][j];
if (j>=eheh[i-1][1]){
dp[i][j]=max(dp[i][j], dp[i-1][j-eheh[i-1][1]]+eheh[i-1][0]);
}
}
}
cout<<dp[eheh.size()][s]<<'\n';
}
int main(){
iamtefu;
#if defined(airths)
auto t1=chrono::high_resolution_clock::now();
freopen("in", "r", stdin);
freopen("out", "w", stdout);
#else
//
#endif
// tt
{
scn();
}
#if defined(airths)
auto t2=chrono::high_resolution_clock::now();
ld ti=chrono::duration_cast<chrono::nanoseconds>(t2-t1).count();
ti*=1e-6;
cerr<<"Time: "<<setprecision(12)<<ti;
cerr<<"ms\n";
#endif
return 0;
}
