#include <iostream>
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn = 2*1e5+5, INF = 4e18+9;
struct item{
ll v, w, k;
};
void solve(){
int s, n;
cin >> s >> n;
vector<item> a(n+1);
for(int i = 1; i <= n; i++){
cin >> a[i].v >> a[i].w >> a[i].k;
}
vector<vector<item>> t(s+1);
for(int i = 1; i <= n; i++){
t[a[i].w].push_back(a[i]);
}
vector<item> b;
for(int i = 0; i <= s; i++){
sort(t[i].begin(), t[i].end(), [&](item a, item b){return a.v > b.v;});
int cnt = 0;
int j = 0;
while(j < (int)t[i].size() && cnt < s/i){
if(t[i][j].k > 0){
b.push_back(t[i][j]);
t[i][j].k--;
cnt++;
}else{
j++;
}
}
}
vector<ll> f(s+1, -INF), prv(s+1, -INF);
f[0] = 0;
for(auto it : b){
prv = f;
fill(f.begin(), f.end(), -INF);
for(int j = 0; j <= s; j++){
f[j] = prv[j];
if(j-it.w >= 0) f[j] = max(f[j], prv[j-it.w]+it.v);
}
}
ll ans = -INF;
for(int j = 0; j <= s; j++){
ans = max(ans, f[j]);
}
cout << ans;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
solve();
}
