#include <iostream>
#include <algorithm>
#include <map>
#include <vector>
using namespace std;
int main() {
int s,n;cin>>s>>n;
map<int, vector<pair<int,int>>> types;
for (int i=0;i<n;i++) {
int v,w,k;
cin>>v>>w>>k;
types[w].push_back({v,k});
}
vector<vector<int>> best(types.size()+1, vector<int>(s+1, 0));
auto curr_type_it = begin(types);
for (size_t i = 1; i <= types.size(); i++) {
auto curr_weight = curr_type_it->first;
auto& curr_type = curr_type_it->second;
sort(begin(curr_type), end(curr_type), greater<>());
for (int w = 0; w <= s; w++) {
best[i][w] = best[i-1][w];
int profit = 0;
size_t idx=0;
int used=0;
for (int j = 1; idx<curr_type.size() && w-j*curr_weight >= 0; j++) {
if (used == curr_type[idx].second) {
idx++;
used =0;
}
if (idx >= curr_type.size())
break;
profit += curr_type[idx].first;
used++;
best[i][w] = max(best[i][w], profit + best[i-1][w-j*curr_weight]);
}
}
curr_type_it = next(curr_type_it);
}
cout << *max_element(begin(best[types.size()]), end(best[types.size()])) << endl;
}
