#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
int S, N;
cin >> S >> N;
map<int, vector<pair<int, int>>> by_weights;
for(int i = 0; i < N; i++){
int val, weight, amt;
cin >> val >> weight >> amt;
by_weights[weight].push_back({val, amt});
}
vector<vector<ll>> best_at(by_weights.size() + 1, vector<ll>(S + 1, INT32_MIN));
best_at[0][0] = 0;
int at = 1;
for(auto &[w, items]: by_weights){
sort(items.begin(), items.end(), greater<pair<int, int>>());
for(int i = 0; i <= S; i++){
best_at[at][i] = best_at[at - 1][i];
int copies = 0;
ll profit = 0;
int curr_used = 0;
int type_at = 0;
while((copies + 1) * w <= i && type_at < items.size()){
copies++;
profit += items[type_at].first;
if(best_at[at - 1][i - copies * w] != INT32_MIN){
best_at[at][i] = max(best_at[at][i], best_at[at - 1][i - copies * w] + profit);
}
curr_used++;
if(curr_used == items[type_at].second){
curr_used = 0;
type_at++;
}
}
}
at++;
}
cout << *max_element(best_at.back().begin(), best_at.back().end()) << '\n';
}
