#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=105,S=2005;
tuple<ll,ll,ll>ar[N+3];
int n,s;
ll dp[N+2][S+2][15];
bool vis[N+3][S+2][15];
ll sol(int i,int w,int k){
if(i>n)return 0;
if(vis[i][w][k])return dp[i][w][k];
vis[i][w][k]=1;
auto[val,ww,num]=ar[i];
ll s1=sol(i+1,w,0);
ll s2=0;
if(k<num){
if(w+ww<=s){
s2=sol(i,w+ww,k+1)+val;
}
}
return dp[i][w][k]=max(s1,s2);
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin>>s>>n;
for(int i=1;i<=n;i++){
ll v,w,k;
cin>>v>>w>>k;
ar[i]={v,w,k};
}
cout<<sol(1,0,0)<<endl;
return 0;
}
