#include <bits/stdc++.h>
using namespace std;
int const MAXN=1e5+5;
int const MAXS=2005;
int total_size,n;
struct food{
int val,w,fr;
bool operator<(food ot){
if(w!=ot.w)
return w<ot.w;
return val>ot.val;
}
}food[MAXN];
void read(){
cin>>total_size>>n;
int i;
for(i=1;i<=n;++i){
int val,w,fr;
cin>>val>>w>>fr;
food[i]={val,w,fr};
}
sort(food+1,food+n+1);
}
int add_val[MAXS];
void maxself(int& x,int val){
if(x<val)
x=val;
}
int dp[MAXS];
int solve(){
dp[0]=0;
int i,j;
for(i=1;i<=total_size;++i)
dp[i]=-1;
int id;
for(id=1;id<=n;){
int curr_w=food[id].w;
int ind_add=0;
while(food[id].w==curr_w){
while(food[id].fr && ind_add<total_size){
--food[id].fr;
add_val[++ind_add]=food[id].val;
}
++id;
}
for(i=total_size;i;--i){
int val_added=0;
for(j=1;j<=ind_add && i-j*curr_w>=0;++j){
val_added+=add_val[j];
maxself(dp[i],dp[i-j*curr_w]+val_added);
}
}
}
int maxim=0;
for(i=1;i<=total_size;++i)
maxself(maxim,dp[i]);
return maxim;
}
int main()
{
read();
cout<<solve();
return 0;
}
