#include <bits/stdc++.h>
using namespace std;
int memo[15523][2005];
int S, N;
int W[15523], V[15523];
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> S >> N;
memset(memo, 0, sizeof(memo));
priority_queue<pair<int, int>> Vp[S];
int v, w, k;
for(int i = 0; i < N; i++){
cin >> v >> w >> k;
w--;
Vp[w].push(make_pair(v, k));
}
k = 0;
for(int i = 0; i < S; i++){
int x = 0;
while (x < S/(i+1) && !Vp[i].empty()){
for(int j = 0; j < Vp[i].top().second; j++){
V[k] = Vp[i].top().first;
W[k] = i+1;
k++;
x++;
if (x >= S/(i+1)) break;
}
Vp[i].pop();
}
}
for(int i = 0; i < k; i++){
for(int j = 1; j < S+1; j++){
if (W[i] <= j){
memo[i+1][j] = max(V[i]+memo[i][j-W[i]], memo[i][j]);
} else {
memo[i+1][j] = memo[i][j];
}
}
}
cout << memo[k][S];
}
