#include<iostream>
#include<algorithm>
#include <string>
#include<iomanip>
#include <map>
#include<vector>
#include <cmath>
#include<set>
#include<stack>
#include<queue>
#include <list>
#include<cstring>
#include<unordered_set>
#include<unordered_map>
#include<utility>
using namespace std;
#define int long long
#define pb push_back
int m1=1e9+7;
int m2=998244353;
int binpow(int a,int b,int m){
int ans=1;
while(b>0){
int r=b%2;
if(r&1){
ans*=a;
ans%=m;
}
a*=a;
a%=m;
b/=2;
}
return(ans);
}
vector<int> fac(1e7+10);
void factorial(){
fac[0]=1;
for(int i=1;i<=1e7+9;i++){
fac[i]=fac[i-1]*i;
fac[i]%=m1;
}
}
void dfs(int node,vector<vector<int>>&ar,vector<int>&vis,vector<int>&par){
vis[node]=1;
for(auto it:ar[node]){
if(vis[it]==0){
vis[it]=1;
par[it]=node;
dfs(it,ar,vis,par);
}
}
}
signed main(){
cout<<setprecision(50);
int t=1;
//cin>>t;
for(int i=0;i<t;i++){
int s,n;
cin>>s>>n;
vector<vector<int>> vf;
for(int i=0;i<n;i++){
int v,w,k;
cin>>v>>w>>k;
vector<int> vtemp;
vf.pb({w,v,k});
}
sort(vf.begin(),vf.end());
map<int,int>mp;
vector<vector<int>> v;
for(int i=n-1;i>=0;i--){
int val= vf[i][1];
int weight=vf[i][0];
int k=min(vf[i][2],(s-mp[weight]*weight)/weight);
mp[weight]+=k;
if(k==0){
continue;
}
v.push_back({weight,val,k});
}
// for(auto it:v){
// cout<<it[0]<<" "<<it[1]<<' '<<it[2]<<'\n';
// }
vector<int> dp(s+1,-1);
dp[0]=0;
for(auto it:v){
for(int j=0;j<it[2];j++){
for(int i=s-it[0];i>=0;i--){
if(dp[i]!=-1){
//cout<<":";
dp[i+it[0]]=max(dp[i+it[0]],dp[i]+it[1]);
//cout<<dp[i+it[0]]<<" ";
}
}
}
}
int mx=0;
for(int i=0;i<=s;i++){
mx=max(mx,dp[i]);
}
cout<<mx<<'\n';
}
}
