#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int s,n;
cin >> s >> n;
vector<vector<pair<int,int>>> hs(s + 1);
for(int i = 0;i < n;i++){
int v,w,k;
cin >> v >> w >> k;
hs[w].push_back({v,k});
}
vector<vector<int>> tot(s + 1);
for(int i = 1;i <= s;i++){
sort(hs[i].begin(),hs[i].end(),greater<pair<int,int>>());
vector<pair<int,int>> vec;
pair<int,int> p = {-1,-1};
for(int j = 0;j < (int)hs[i].size();j++){
if(p.first != hs[i][j].first){
if(p.first != -1){
vec.push_back(p);
}
p = hs[i][j];
}else{
p.second += hs[i][j].second;
}
}
if(p.first != -1) vec.push_back(p);
hs[i] = vec;
int num = 0;
for(pair<int,int> p : hs[i]){
if(num == s / i) break;
for(int j = 0;j < p.second;j++){
tot[i].push_back(p.first);
num ++;
if(num == s / i) break;
}
}
while(tot[i].size() < s / i) tot[i].push_back(0);
}
// for(int i = 1;i <= s;i++){
// cout << i << " : \n";
// for(pair<int,int> &e : hs[i]){
// cout << e.first << " " << e.second << '\n';
// }
// }
// vector<vector<i64>> dp(s + 2,vector<i64>(s + 2));
// if currently at (i,j) -> ith weight,s space left
// vector<vector<vector<i64>>> dp(s + 2,vector<vector<i64>>(s + 1));
// for(int i = 1;i <= s + 1;i++){
// for(int j = 0;j <= s;j++){
// dp[i][j] = vector<i64>((s / i) + 5);
// }
// }
vector<vector<i64>> dp,ndp;
ndp = vector<vector<i64>>(s + 1,vector<i64>(5));
for(int i = s;i >= 1;i--){
dp = vector<vector<i64>>(s + 1,vector<i64>((s / i) + 5));
for(int k = (s / i);k >= 0;k--){
for(int j = i;j <= s;j++){
// take
if(k < (int) tot[i].size()) dp[j][k] = dp[j - i][k + 1] + tot[i][k];
// not take
dp[j][k] = max(dp[j][k],ndp[j][0]);
}
}
ndp = dp;
}
cout << dp[s][0] << '\n';
return 0;
}
