#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define forn(i,n) for(int i = 0;i<int(n);i++)
#define dforn(i,n) for(int i = int(n)-1;i>=0;i--)
#define forsn(i,s,n) for(int i = int(s);i<int(n);i++)
#define fore(i,s,n) for(int i = int(s);i<int(n);i++)
#define dforsn(i,s,n) for(int i = int(n)-1;i>=int(s);i--)
#define DBG(x) do{cout<<#x<<" = "<<x<<endl;}while(false)
#define TAM_MASK 1
#define get(mask,i) ((mask>>(TAM_MASK*(i)) & ( (1<<TAM_MASK)-1)))
#define set(mask,i,v) ( ((mask & ~( ( (1<<TAM_MASK)-1) << (TAM_MASK*(i)) )) | (v<<(TAM_MASK * (i))) ))
#define popcount(mask) (__builtin_popcount(mask))
#define endl '\n'
#define ALL(x) x.begin(),x.end()
template<class T> ostream & operator<<(ostream & out, vector<T> & v)
{
out<<"[";
for(auto k : v) out<<k<<",";
out<<"]"<<"\n";
return out;
}
template<class T> ostream & operator<<(ostream & out, set<T> s)
{
out<<"{";
for(auto k : s) out<<k<<",";
out<<"}"<<"\n";
return out;
}
template<class T, class U> ostream & operator<<(ostream & out, pair<T,U> p)
{
out<<"[ "<<p.first<<" , "<<p.second<<" ] ";
return out;
}
template<class T, class U> istream & operator>>(istream & in, pair<T,U> & p)
{
in>>p.first>>p.second;
return in;
}
typedef long long intl;
const int maxs = 2005;
vector<pair<int,int> > ins[maxs];
vector<pair<int,int> > in;
intl dp[maxs];
int main()
{
cin.tie(0);
cin.sync_with_stdio(0);
int S,N;
cin>>S>>N;
forn(i,N){
int v,w,k;
cin>>v>>w>>k;
ins[w].pb({v,k});
}
forsn(i,1,maxs){
sort(ins[i].begin(),ins[i].end());
int t = S/i + 1;
while(t and ins[i].size()){
in.pb({i,ins[i].back().first});
ins[i].back().second--;
if(ins[i].back().second==0)
ins[i].pop_back();
t--;
}
}
for(auto pp : in){
int w = pp.first;
int v = pp.second;
dforn(i,S-w+1){
dp[i+w] = max(dp[i+w],dp[i]+v);
}
}
intl res = 0;
forn(i,S+1) res = max(res,dp[i]);
cout<<res<<endl;
}
