#include "bits/stdc++.h"
using namespace std;
#define rep(i, a, b) for (auto i = a; i < b; i++)
#define sz(x) static_cast<long long>((x).size())
#define all(x) (x).begin(), (x).end()
// #ifndef ONLINE_JUDGE
// #include "debug.h"
// #endif
#define int long long
#define double long double
const long long inf = (long long) 1e18;
const long long inf2 = LONG_LONG_MAX/2 - 100;
const long long mod = (int)1e9 + 7;
int32_t main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout << fixed << setprecision(10);
int w, n; cin >> w >> n;
vector<vector<int>> v[w+1];
rep(i, 0, n){
int x, y, z; cin >> x >> y >> z;
v[y].push_back({x, z});
}
rep(i, 1, w+1) sort(v[i].begin(), v[i].end());
vector<vector<int>> a;
for(int i = 1; i <= w; i++){
int r = w/i + 5;
for(int j = 0; j < r; j++){
if(v[i].empty()) break;
a.push_back({v[i].back()[0], i});
v[i].back()[1]--;
if(v[i].back()[1] == 0) v[i].pop_back();
}
}
n = sz(a);
vector<int> dp(w+1, 0), prevdp(w+1, 0);
for(int i = 0; i < n; i++){
for(int j = 0; j <= w; j++){
if(i == 0){
if(j == a[i][1]) dp[j] = a[i][0];
}
else{
dp[j] = prevdp[j];
if(j >= a[i][1]) dp[j] = max(dp[j], prevdp[j-a[i][1]] + a[i][0]);
}
}
prevdp = dp;
dp.assign(w+1, 0);
}
int ans = *max_element(all(prevdp));
cout << ans << '\n';
}
