#include <bits/stdc++.h>
using namespace std;
const int maxs=2e3+10;
vector<pair<int,int>>op[maxs];
int dp[maxs];
int main()
{
ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
int s, n; cin >> s >> n;
for(int i=1;i<=n;i++){
int a, b, c; cin >> a >> b >> c;
op[b].push_back({a,c});
}
vector<pair<int,int>>process;
for(int i=1;i<=s;i++){
int m=(s/i), at=1;
sort(op[i].begin(),op[i].end());
while(at<=m&&op[i].size()){
at++;
int sz=op[i].size()-1;
op[i][sz].second--;
process.push_back({op[i].back().first,i});
if(op[i][sz].second==0) op[i].pop_back();
}
}
int resp=0;
for(auto p : process){
for(int i=s;i>=p.second;i--){
dp[i]=max(dp[i],dp[i-p.second]+p.first);
resp=max(resp,dp[i]);
}
}
cout << resp << endl;
return 0;
}
