#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf = 1e18;
// Try to accurately compute the time complexity
// Also remember 1/1 + 1/2 + 1/3 + ... + 1/n = log(n) [approx]
void solve(){
int limit, type_num;
cin >> limit >> type_num;
map<int, vector<pair<int, int>>> by_weight;
for(int t = 0; t < type_num; t++){
int val, wt, amt;
cin >> val >> wt >> amt;
if(wt <= limit && amt > 0) by_weight[wt].push_back({val, amt});
}
/*
* best[i][j] contains the most value we can
* get using j weight and the first i weight types
*/
vector<vector<int>> best(by_weight.size() + 1, vector<int> (limit + 1, -inf));
best[0][0] = 0;
int at = 1;
for(auto &[wt, items] : by_weight){
sort(items.begin(), items.end(), greater<pair<int, int>>());
for(int i = 0; i <= limit; i++){
best[at][i] = best[at - 1][i];
int copies = 0, type_at = 0, curr_used = 0, profit = 0;
while((copies + 1)*wt <= i && type_at < items.size()){
copies++;
profit += items[type_at].first;
if(best[at - 1][i - copies*wt] != -inf){
best[at][i] = max(best[at][i], best[at - 1][i - copies*wt] + profit);
}
curr_used++;
if(curr_used == items[type_at].second){
curr_used = 0;
type_at++;
}
}
}
at++;
}
cout << *max_element(best.back().begin(), best.back().end()) << endl;
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t = 1;
while(t--) solve();
return 0;
}
