#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FOD(i,a,b) for(int i=a;i>=b;i--)
#define MASK(mask,n) for(int mask=0;mask<(1<<n);mask++)
#define SUB(submask,mask) for(int submask=(mask-1)&mask;submask>0;submask=(submask-1)&mask)
#define pb push_back
#define sz(a) ((int)a.size()-1)
clock_t start,finish;
const int MOD=1e9+7;
const int Nall=1e5+5;
int n,s,V[Nall],W[Nall],K[Nall];
int add(int a,int b){return a+b>=MOD?a+b-MOD:a+b;}
namespace subcheck{
bool sub1(){return n==1;}
bool sub2(){
FOR(i,1,n){
if(K[i]>1) return 0;
}
return n<=100;
}
bool sub3(){
FOR(i,1,n){
if(K[i]>10) return 0;
}
return n<=100;
}
bool sub4(){
return n<=100;
}
}
namespace sub1{
void solve(){
cerr<<"SUB1";
cout<<min(K[1],s/W[1])*V[1];
}
}
namespace sub2{
const int N=1e2+5,S=2e3+5;
int Dp[N][S];
void solve(){
cerr<<"SUB2 ";
int res=0;
if(W[1]<=s) Dp[1][W[1]]=V[1],res=V[1];
FOR(i,2,n){
FOR(j,1,i-1){
FOR(w,1,s){
if(w-W[i]>=0) Dp[i][w]=max(Dp[i][w],Dp[j][w-W[i]]+V[i]);
}
}
FOR(w,1,s) res=max(res,Dp[i][w]);
}
cout<<res;
}
}
namespace sub3{
const int S=2e3+5,N=1e3+5;
int Dp[N][S];
void solve(){
cerr<<"SUB3 ";
int m=n;
FOR(i,1,n){
K[i]--;
while(K[i]--){V[++m]=V[i],W[m]=W[i];}
}
FOR(w,W[1],s) Dp[1][w]=V[1];
FOR(i,2,m){
FOR(w,1,s){
Dp[i][w]=max(Dp[i][w-1],Dp[i-1][w]);
if(w-W[i]>=0) Dp[i][w]=max(Dp[i][w],Dp[i-1][w-W[i]]+V[i]);
}
}
cout<<Dp[m][s];
}
}
namespace sub4{
const int S=2e3+5,N=2e4+5;
int Dp[N][S];
void solve(){
int m=n;
FOR(i,1,n){
K[i]=min(K[i],s/W[i]);
K[i]--;
while(K[i]--){V[++m]=V[i],W[m]=W[i];}
}
FOR(w,W[1],s) Dp[1][w]=V[1];
FOR(i,2,m){
FOR(w,1,s){
Dp[i][w]=max(Dp[i][w-1],Dp[i-1][w]);
if(w-W[i]>=0) Dp[i][w]=max(Dp[i][w],Dp[i-1][w-W[i]]+V[i]);
}
}
cout<<Dp[m][s];
}
}
signed main(){
start=clock();
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>s>>n;
FOR(i,1,n) cin>>V[i]>>W[i]>>K[i];
if(subcheck::sub1()) return sub1::solve(),0;
if(subcheck::sub2()) return sub2::solve(),0;
if(subcheck::sub3()) return sub3::solve(),0;
if(subcheck::sub4()) return sub4::solve(),0;
return 0;
}
