#include <bits/stdc++.h>
using namespace std;
bool cmppairpair(pair<int,pair<int,int>> a, pair<int,pair<int,int>> b) {
return a.first > b.first;
}
int main() {
int s,n; cin >> s >> n;
vector<pair<int,pair<int,int>>> items(n); for (int i = 0; i < n; i++) cin >> items[i].first >> items[i].second.first >> items[i].second.second;
sort(items.begin(),items.end(),cmppairpair);
vector<vector<int64_t>> fir(s+1,vector<int64_t>(s+1,0));
vector<int> currpointers(s+1,0);
for (int i = 0; i < n; i++) {
pair<int,pair<int,int>> curr = items[i];
if (curr.second.first < s) {
for (int j = 0; j < curr.second.second; j++) {
if (currpointers[curr.second.first] == s) break;
fir[curr.second.first][currpointers[curr.second.first]+1] = curr.first+fir[curr.second.first][currpointers[curr.second.first]];
currpointers[curr.second.first]++;
}
}
}
vector<vector<int64_t>> dp(s+1,vector<int64_t>(s+1,0));
for (int i = 1; i <= s; i++) {
for (int j = 1; j <= s; j++) {
dp[i][j] = max(dp[i][j-1],dp[i-1][j]);
int k = 1;
while (i*k <= j && fir[i][k] != 0) {
dp[i][j] = max(dp[i][j],dp[i-1][j-i*k]+fir[i][k]);
k++;
}
}
}
cout << dp[s][s] << endl;
}
