#include <bits/stdc++.h>
using namespace std;
typedef int ll;
vector<vector<ll>> DP;
vector<vector<pair<ll, ll>>> b;
vector<pair<ll, ll>> a;
ll calc(ll w, ll x){
if(DP[w][x] != -1){return DP[w][x];}
if(x==0){return DP[w][x] = 0;}
if(w<a[x].first){return DP[w][x] = calc(w, x-1);}
return DP[w][x] = max(calc(w-a[x-1].first, x-1)+a[x-1].second, calc(w, x-1));
}
int main() {
ll S, N, v, w, k;
cin>>S>>N;
b.resize(S+1);
for(ll i=0;i<N;i++){
cin>>v>>w>>k;
b[w].push_back({-v, k});
}
for(ll i=1;i<S;i++){
sort(b[i].begin(), b[i].end());
if(b[i].size() == 0){continue;}
ll ind = 0;
k = b[i][ind].second;
for(ll j=i;j<S;j+=i){
a.push_back({i, -b[i][ind].first});
k--;
if(k==0){
ind++;
if(ind == b[i].size()){break;}
k = b[i][ind].second;
}
}
}
DP.resize(S+1, vector<ll>(a.size()+1, -1));
cout<<calc(S, a.size());
}
