#include <bits/stdc++.h>
using namespace std;
#define fastIO ios_base::sync_with_stdio(false), cin.tie(NULL)
#define forw(i,l,r) for(int i=l; i<r; i++)
#define fore(i,l,r) for(int i=l; i<=r; i++)
#define forb(i,r,l) for(int i=r; i>=l; i--)
#define rep(i,n) forw(i,0,n)
#define numBit(x) (__builtin_popcountll(1ll*x))
#define getBit(x,i) ((x&(1<<i))?1:0)
#define Pi acos(-1.0l)
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define pob pop_back
#define pf push_front
#define pof pop_front
#define ins insert
#define sz(a) int(a.size())
#define all(a) a.begin(),a.end()
#define ALLBITS ~0
typedef long long ll;
typedef unsigned long long int ulli;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<int,ll> pill;
typedef pair<ll,int> plli;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef vector<pii> vpii;
template<class X, class Y>
bool maximize(X &x, const Y &y){
X eps=1e-9;
if(x+eps<y){
x=y; return true;
}
return false;
}
template<class X, class Y>
bool minimize(X &x, const Y &y){
X eps=1e-9;
if(x>y+eps){
x=y; return true;
}
return false;
}
template<class X>
X Abs(const X &x){
return (x>0)?(x):(-x);
}
/*-------------------MAIN PROGRAM------------------*/
const int MAXCAP=2007;
const ll INF=1e18;
int cap, n;
vpii grp[MAXCAP];
ll f[MAXCAP][MAXCAP];
void read(){
cin>>cap>>n;
while(n--){
int v, w, k; cin>>v>>w>>k;
grp[w].pb(mp(v,k));
}
}
void solve(){
rep(i,MAXCAP) rep(j,MAXCAP) f[i][j]=-INF;
f[0][0]=0;
ll ans=0;
fore(curW,1,cap){
f[curW][0]=0;
sort(all(grp[curW]),greater<pii>());
fore(lim,1,cap){
f[curW][lim]=f[curW-1][lim];
ll sum=0;
int num=0, pos=0, used=0;
while((num+1)*curW<=lim && pos<sz(grp[curW])){
num++;
sum+=grp[curW][pos].fi;
if(f[curW-1][lim-num*curW]>=0)
maximize(f[curW][lim],
f[curW-1][lim-num*curW]+sum);
used++;
if(used==grp[curW][pos].se){
pos++;
used=0;
}
}
maximize(ans,f[curW][lim]);
}
}
cout<<ans;
}
int main(){
fastIO;
read();
solve();
return 0;
}
