#include<bits/stdc++.h>
using namespace std;
struct s{int v,w,k;}a[(int)1e5];
vector<array<int,2>>b;
vector<int>v[2001];
int f[2001];
bool cmp(const s&a,const s&b){
return(a.v>b.v);
}
int main(){
int m,n;
cin>>m>>n;
for(int i=0;i<n;++i){
cin>>a[i].v>>a[i].w>>a[i].k;
a[i].k=min(a[i].k,m/a[i].w);
}
sort(a,a+n,cmp);
for(int i=0;i<n;++i){
while(a[i].k--&&v[a[i].w].size()<=(m/a[i].w))
v[a[i].w].push_back(a[i].v);
}
for(int w=1;w<=m;++w)
for(int x:v[w])
b.push_back({x,w});
n=b.size();
for(int i=0;i<n;++i){
for(int j=m;j>=b[i][1];--j)
f[j]=max(f[j],f[j-b[i][1]]+b[i][0]);
}
cout<<*max_element(f,f+m+1);
}
