#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define fi first
#define se second
#define INF 1000000009
bool comp(pair<int,int> a, pair<int,int> b) {
return a.fi > b.fi;
}
int main() {
int s, n;
cin >> s >> n;
vector<vector<pair<int,int>>> val(s + 1);
for(int i = 0; i < n; ++i) {
int v, w, k;
cin >> v >> w >> k;
val[w].push_back(make_pair(v, k));
}
for(int i = 1; i <= s; ++i) {
sort(val[i].begin(), val[i].end(), comp);
}
vector<int> dp(s + 1, -INF);
dp[0] = 0;
for(int i = 1; i <= s; ++i) {
int used_space = 0;
for(pair<int,int> item : val[i]) {
for(int c = 1; c <= item.se; ++c) {
used_space += i;
for(int leftover_space = s; leftover_space >= used_space; --leftover_space) {
dp[leftover_space] = max(dp[leftover_space], dp[leftover_space - i] + item.fi);
}
if(used_space > s) {
break;
}
}
if(used_space > s) {
break;
}
}
}
int answer = 0;
for(int i = 1; i <= s; ++i) {
answer = max(answer, dp[i]);
}
cout << answer << endl;
}
