#include <bits/stdc++.h>
using namespace std;
void subtask_1(int wmax,int n, vector<int> v, vector <int> w, vector <int> k){cout<<min(k[0],wmax/w[0])*v[0];}
void subtask_2(int wmax,int n, vector<int> v, vector <int> w, vector <int> tt){
int dp[wmax+1];
for (int i=0; i<=wmax; i++){dp[i]=-1;}
dp[0]=0;
for (int i=0; i<n; i++){
for (int j=wmax; j>=0; j--){
if (dp[j]!=-1){
int t=1;
for (int k=j+w[i]; t<=tt[i] && k<=wmax; k+=w[i]){
dp[k]=max(dp[k],dp[j]+t*v[i]);
t++;
}
}
}
}
int mx=0;
for (int i=0; i<=wmax; i++){
mx=max(mx,dp[i]);
}
cout<<mx;
}
void subtask_3(int wmax,int n, vector<int> v, vector <int> w, vector <int> tt){
vector <pair<int,pair<int,int>>> baraa;
for (int i=0; i<n; i++){
baraa.push_back({w[i],{v[i],tt[i]}});
}
sort(baraa.begin(),baraa.end(),[](auto &a, auto &b){
if (a.first==b.first){
return b.second.first<a.second.first;
}
return a.first<b.first;
});
vector <int> bst[2001];
for (int i=0; i<n; i++){
if (baraa[i].first<2001){
for (int j=0; j<baraa[i].second.second && bst[baraa[i].first].size()<=2000; j++){
bst[baraa[i].first].push_back(baraa[i].second.first);
}
}
}
int dp[wmax+1];
for (int i=0; i<=wmax; i++){dp[i]=-1;}
dp[0]=0;
for (int i=1; i<2001; i++){
for (int j=wmax; j>=0; j--){
if (dp[j]!=-1){
int t=1;
int sm=0;
for (int k=j+i; k<=wmax && k-j-i<bst[i].size(); k+=i){
dp[k]=max(dp[k],dp[j]+sm+bst[i][k-j-i]);
t++;
sm+=bst[i][k-j-i];
}
}
}
}
int mx=0;
for (int i=0; i<=wmax; i++){
mx=max(mx,dp[i]);
}
cout<<mx;
}
int main(){
int wmax,n;
cin>>wmax>>n;
vector <int> V(n),W(n),K(n);
for (int i=0; i<n; i++){
cin>>V[i]>>W[i]>>K[i];
}
if (n==1)subtask_1(wmax,n,V,W,K);
else if(n<=100){subtask_2(wmax,n,V,W,K);}
else{subtask_3(wmax,n,V,W,K);}
}
