#include <bits/stdc++.h>
#define fi first
#define se second
#define int long long
using namespace std;
using ll = long long;
using ii = pair<int,int>;
using pii = pair<int,ii>;
using aa = array<int,3>;
const int N = 2005;
const int M = 1e5+5;
const int INF = 1e9;
const int MOD = 1e9+7;
int n, S, x, y, z, ans = 0, a[M];
int dp[N][N];
vector <ii> adj[N];
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> S >> n;
for (int i = 1; i <= n; i++){
cin >> x >> y >> z;
adj[y].push_back({x,z});
}
for (int i = 0; i <= S; i++){
for (int j = 0; j <= S; j++) dp[i][j] = -1;
}
dp[0][0] = 0;
int cnt = 0;
for (int i = 1; i <= S; i++){
if (adj[i].empty()) continue;
cnt++;
sort(adj[i].begin(),adj[i].end(),greater<ii>());
for (int k = 0; k <= S; k++){
dp[cnt][k] = dp[cnt-1][k];
int cur = 0;
int tmp = 0;
int sum = 0;
int prev = 0;
while ((cur + 1) * i <= k && tmp < (int)adj[i].size()){
cur++;
sum += adj[i][tmp].fi;
if (dp[cnt-1][k - cur * i] != -1){
dp[cnt][k] = max(dp[cnt][k],dp[cnt-1][k - cur * i] + sum);
}
if (cur - prev == adj[i][tmp].se){
prev = adj[i][tmp].se;
tmp++;
}
}
}
}
for (int i = 0; i <= cnt; i++){
for (int j = 1; j <= S; j++) ans = max(ans,dp[i][j]);
}
cout << ans;
return 0;
}
