#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
int s, n;
map<int, vector<pii>> sorban;
vector<vector<int>> dp;
vector<int> indexek;
int megold(int ind, int maradt){
if(maradt < 0){
return 0;
}
if(ind == (int)sorban.size()){
return 0;
}
if(dp[ind][maradt] != -1){
return dp[ind][maradt];
}
int vissza = 0;
int plusz = 0;
int minusz = 0;
for(int i = 0; i < (int)sorban[indexek[ind]].size(); i++){
for(int j = 0; j < sorban[indexek[ind]][i].second; j++){
minusz += indexek[ind] + 1;
plusz += sorban[indexek[ind]][i].first;
int a = (maradt - minusz >= 0 ? megold(ind + 1, maradt - minusz) + plusz : 0);
//cout << ind << " " << maradt << " : " << a << " : " << plusz << " " << minusz << "\n";
vissza = max(vissza, a);
}
}
return dp[ind][maradt] = vissza;
}
int main(){
cin >> s >> n;
for(int i = 0; i < n; i++){
int ertek, suly, db;
cin >> ertek >> suly >> db;
if(sorban[suly - 1].size() == 0){
indexek.push_back(suly - 1);
}
sorban[suly - 1].push_back({ertek, db});
}
sort(indexek.begin(), indexek.end());
dp.assign(sorban.size(), vector<int>(s + 1, -1));
for(auto &x : sorban){
sort(x.second.begin(), x.second.end(), greater<pii>());
}
cout << megold(0, s) << "\n";
}
