#include <bits/stdc++.h>
using namespace std;
#define int long long
int32_t main() {
int s, n;
cin >> s >> n;
int items[n][3];
for(int i=0; i<n; ++i) cin >> items[i][0] >> items[i][1] >> items[i][2], items[i][2]=min(items[i][2], s/items[i][1]);
priority_queue<pair<int, int>> pque[s+1];
for(int i=0; i<n; ++i) pque[items[i][1]].push({items[i][0], items[i][2]});
vector<pair<int, int>> final_items;
for(int i=1; i<=s; ++i) {
int amount=0;
while(!pque[i].empty() && amount+1<=s/i) {
final_items.push_back({i, pque[i].top().first});
auto top=pque[i].top();
pque[i].pop();
if(top.second>1) pque[i].push({top.first, top.second-1});
amount++;
}
}
int knapsack[s+1]={};
int sizes=final_items.size();
for(int i=0; i<sizes; ++i) {
//cout << final_items[i].first << " " << final_items[i].second;
for(int j=s; j>=0; --j) {
if(final_items[i].first+j<=s) {
knapsack[final_items[i].first+j]=max(knapsack[final_items[i].first+j], knapsack[j]+final_items[i].second);
}
}
}
int ans=0;
for(auto &elem:knapsack) {
//cout << elem << " ";
ans=max(ans, elem);
}
cout << ans;
return 0;
}
