#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pr pair<int, int>
#define f first
#define s second
ll n, s;
bool cmp(pr a, pr b){
return a.f> b.f;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin>>s>>n;
vector<ll> dp(s+1, -1);
vector<vector<pr>> list(2001);
for (int i=0; i<n; i++){
int vi, wi, ki; cin>>vi>>wi>>ki;
list[wi].push_back({vi, ki});
}
// sort the items per values from top to bottom with the same weight
for (int i=1; i<=s; i++){
if(list[i].size()>0) sort(list[i].begin(), list[i].end(), cmp);
}
// now using the standard knapsack to calculate the problem
dp[0]=0;
for (int i=1; i<=s; i++){ // convert to weight dim
if(list[i].size()<=0) continue; // empty weight item
int weight=0;
for (int j=0; j<(int)list[i].size(); j++){ // this is the same weight, value group #
for (int j1=0; j1<list[i][j].s && weight<=s; j1++){
weight+=i; // total weight until this point
for (int k=s; k>=i; k--){
if(dp[k-i]>=0 ) {
dp[k]=max(dp[k], dp[k-i]+list[i][j].f);
}
}
}
}
}
ll mval=0;
for (int i=0; i<=s; i++) mval=max(mval, dp[i]);
cout<<mval;
}
