#include <bits/stdc++.h>
#define int long long
int value[100010];
int weight[100010];
int amount[100010];
int dpw[2010];//most cost secured from the weight
std::map<int,int> wv[2010];
signed main(){
int s,n;
std::cin >> s >> n;
for(int i=1;i<=n;i++){
std::cin >> value[i] >> weight[i] >> amount[i];
wv[weight[i]][-value[i]]+=amount[i];
}
for(int k=1;k<=s;k++){
int arraysize = (((double)s/k) + 1);
std::vector<int> checkV;
for(auto &p:wv[k]){
for(int i=0;i<p.second;i++){
checkV.push_back(-p.first);
if(checkV.size()>arraysize){
break;
}
}
if(checkV.size()>arraysize){
break;
}
}
for(auto vc:checkV){
for(int i=s;i>=k;i--){
dpw[i]=std::max(dpw[i-k]+vc,dpw[i]);
}
}
}
//for(int i=0;i<=s;i++)std::cout << dpw[i] << ' ';
std::cout << dpw[s];
}
