#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
int maxkilo,noitems;
cin>>maxkilo>>noitems;
vector<pair<int,pair<int,int>>> value(noitems);
for(int i = 0;i<noitems;i++){
cin>>value[i].second.first>>value[i].second.second>>value[i].first;
}
vector<vector<int>> dp(noitems+1,vector<int>(maxkilo+1,0));
int maxi = 0;
for(int i =1;i<noitems+1;i++){
vector<int> howmany(maxkilo+1,0);
for(int j = 1;j<maxkilo+1;j++){
int take = 0;
int nottake = dp[i-1][j];
if(value[i-1].second.second <= j){
take = value[i-1].second.first+dp[i-1][j-value[i-1].second.second];
if(value[i].first >1){
int take2 = value[i-1].second.first+dp[i][j-value[i-1].second.second];
if(take2 >take){
howmany[j] = howmany[j-value[i-1].second.second]+1;
if(howmany[j] >= value[i].first){
take2 = 0;
}
}else{
howmany[j] = 1;
}
take = max(take,take2);
}
}
if(nottake >= take){
howmany[j] = 0;
}
dp[i][j] = max(take,nottake);
maxi = max(maxi,dp[i][j]);
}
}
cout<<maxi<<endl;
return 0;
}
