//we are all lost trying to be someone.
#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0); cin.tie(0);
#define sz(x) ll(x.size())
#define reve(x) reverse(x.begin(),x.end())
#define ff first
#define ss second
#define pb push_back
using namespace std;
#define trace(...) fff(#__VA_ARGS__, __VA_ARGS__)
template<typename t> void fff(const char* x, t&& val1) { cout<<x<< " : "<<val1<<"\n";}
template<typename t1, typename... t2> void fff(const char* x, t1&& val1, t2&&... val2){
const char* xd=strchr(x+1, ',');
cout.write(x, xd-x)<<" : "<<val1<<" | ";
fff(xd+1, val2...);
}
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> ii;
typedef pair<ll, ii >tri;
const ll MAX=1e5+100;
const ll mod=1e9+7;
const ll inf=1e9;
ll dp[2010][MAX];
vector<ii> s[MAX];
ll V[MAX], W[MAX];
void solve(){
ll S, n;
cin>>S>>n;
for(ll i=1; i<=n; i++){
ll v,w,k;
cin>>v>>w>>k;
s[w].push_back({v,k});
}
ll ns=1;
for(ll i=S; i>=1; i--){
sort(s[i].rbegin(),s[i].rend());
ll aux=S/i;
for(ll j=0; j<sz(s[i]); j++){
ll k=s[i][j].ss;
while(aux and k){
V[ns]=s[i][j].ff;
W[ns]=i;
ns++;
aux--;
k--;
}
}
}
memset(dp, -1, sizeof dp);
dp[0][0]=0;
for(ll i=1; i<=ns; i++){
for(ll j=0; j<=S; j++){
dp[i][j]=dp[i-1][j];
if(j-W[i]>=0 and dp[i-1][j-W[i]]!=-1){
dp[i][j]=max(dp[i][j],dp[i-1][j-W[i]]+V[i]);
}
dp[i][j]=max(dp[i][j],dp[i][j-1]);
}
}
cout<<dp[ns][S]<<'\n';
}
int main(){
fastio;
solve();
return 0;
}
