#include <bits/stdc++.h>
using namespace std;
struct ele {
int index;
int value;
int weight;
int number;
};
vector<ele> items;
int main() {
int s,n;
cin>>s>>n;
vector<vector<int>> weights(s+1);
items.resize(n);
for(int i=0;i<n;i++) {
items[i].index = i;
cin>>items[i].value>>items[i].weight>>items[i].number;
}
for(auto it : items) {
weights[it.weight].push_back(it.index);
}
for(int i=1;i<=s;i++) {
sort(weights[i].begin(), weights[i].end(), [](const int a, const int b) {
return items[a].value > items[b].value;
});
// for(auto it : weights[i])
// cout<<it<<' ';
// cout<<'\n';
}
vector<int> result(s+1);
vector<unordered_map<int,int>> how(s+1);
result[0] = 0;
for(int i=1;i<=s;i++) {
result[i] = result[i-1];
int w = 1, ind = -1;
// cout<<"i: "<<i<<'\n';
for(int j=1;j<=i;j++) {
if(weights[j].empty()) continue;
int item_index = 0;
int res = 0;
for(int index : weights[j]) {
// cout<<" index: "<<index<<'\n';
if(how[i-j].count(index) && how[i-j][index] >= items[index].number) continue;
res = result[i-j] + items[index].value;
if(res < result[i]) break;
item_index = index;
break;
}
if(res > result[i]) {
result[i] = res;
w = j;
ind = item_index;
}
}
how[i] = how[i-w];
if(ind != -1)
how[i][ind]++;
// cout<<"i: "<<i<<" result: "<<result[i]<<'\n';
}
cout<<result[s]<<'\n';
}
