#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
typedef long long ll;
using namespace __gnu_pbds;
#define endl '\n'
#define hitaf ios_base::sync_with_stdio(false); cin.tie(0);
#define fi first
#define se second
template <typename T>
using ordered_set = tree<T,null_type,less<T>,rb_tree_tag, tree_order_statistics_node_update>;
const ll MOD = 1e9 + 7;
const ll MOD1 = 998244353;
const ll INF = 4500000000000000000LL;
const ll INF1 = 1e18;
const ll mod1 = 6900000469;
const ll mod2 = 698000002369;
const int block = 160;
int n, m, k, q, a[1200005], b[500005], c[500005];
string s, s1, s2;
int main() {
hitaf
int T = 1;
// cin >> T;
while(T--){
cin >> m >> n;
for(int i = 1; i <= n; i++) cin >> a[i] >> b[i] >> c[i];
vector<vector<pair<ll, ll>>> val(m + 2);
for(int i = 1; i <= n; i++){
val[b[i]].push_back({a[i], c[i]});
}
vector<ll> dp(m + 2, -INF);
dp[0] = 0;
for(int i = 1; i <= m; i++){
sort(val[i].begin(), val[i].end(), [&](pair<ll, ll> x, pair<ll, ll> y){
if(x.fi == y.fi) return x.se > y.se;
return x.fi > y.fi;
});
vector<ll> pref(m + 2);
ll sum = 0, lst = 0;
for(int j = i, idx = 0; j <= m && idx < val[i].size(); j += i){
sum += val[i][idx].fi;
val[i][idx].se--;
if(val[i][idx].se == 0){
idx++;
}
pref[j] = sum;
lst = j;
}
for(int j = m; j >= 0; j--){
for(int k = lst; k >= 0; k -= i){
if(j < k) continue;
dp[j] = max(dp[j], dp[j - k] + pref[k]);
}
}
}
ll maks = 0;
for(int j = 0; j <= m; j++) maks = max(maks, dp[j]);
cout << maks << endl;
}
}
/*
8 3 4 2 1 5 7 6
1 5 6 7 2 4 3 8
*/
