#include <bits/stdc++.h>
using namespace std;
vector<vector<vector<int>>>dp;
int solve(int idx,int sum,int rem_k,vector<int>&v,vector<int>&w,vector<int>&k){
int n=v.size();
if(dp[idx][sum][rem_k]!=0)return dp[idx][sum][rem_k];
if(idx==n || sum==0)return 0;
int value1=solve(idx+1,sum,(idx+1)<n?k[idx+1]:0,v,w,k);
int value2=0;
if(w[idx]<=sum && k[idx]>0){
k[idx]-=1;
value2=v[idx] + solve(idx,sum-w[idx],rem_k-1,v,w,k);
k[idx]+=1;
}
return dp[idx][sum][rem_k]=max(value1,value2);
}
int main() {
int s,n;
cin>>s>>n;
vector<int>v(n);
vector<int>w(n);
vector<int>k(n);
for(int i=0;i<n;i++)cin>>v[i]>>w[i]>>k[i];
dp.assign(n+1,vector<vector<int>>(s+1,vector<int>(51,0)));
cout<<solve(0,s,k[0],v,w,k)<<endl;
}
