#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=1e5+3;
int s,n;
int v[maxn];
int w[maxn];
int k[maxn];
int memo[maxn][2003];
int dp2(int a,int b){
if(a==n+1)return 0;
if(memo[a][b]!=-1)return memo[a][b];
int res;
res=dp2(a+1,b);
if(b>=w[a]){
res=max(res,dp2(a+1,b-w[a])+v[a]);
}
memo[a][b]=res;
return res;
}
int dp(int ke,int berat,int banyak){
if(ke==n+1)return 0;
if(memo[ke][berat]!=-1)return memo[ke][berat];
int &res=memo[ke][berat];
if(banyak>=0 && w[ke]<=berat){
res=max(dp(ke,berat-w[ke],banyak-1)+v[ke],dp(ke+1,berat,k[ke+1]));
}
else{
res=dp(ke+1,berat,k[ke+1]);
}
return res;
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
memset(memo,-1,sizeof memo);
cin>>s>>n;
for(int m=1;m<=n;m++){
cin>>v[m]>>w[m]>>k[m];
}
if(n==1){
cout<<dp(1,s,v[1]);
}
else{
cout<<dp2(1,s);
}
}
