#include<iostream>
using namespace std;
long long w[10005],v[10005],s[10005],f[10005],m,n,idx=1;
int main(){
cin>>m>>n;
for(int i=1;i<=n;i++){
int ww,vv,ss;
cin>>ww>>vv>>ss;
for(int j=1;j<=ss;j++){
w[idx]=ww;
v[idx]=vv;
idx++;
}
}
for(int i=1;i<idx;i++){
for(int j=m;j>=w[i];j--){
f[j]=max(f[j],f[j-w[i]]+v[i]);
}
}
cout<<f[m];
return 0;
}
