#include <bits/stdc++.h>
using namespace std;
#ifndef my_dbg
#define dbg(...) 1337
#else
#include "debug.h"
#endif
const long long mod=1e9+7,inf=2e9+228,infll=LLONG_MAX-1e9;
typedef long long ll;
typedef long double ld;
template<typename T, typename Q> ll binPow(T n,Q k) {ll res=1,a=(ll)n,b=(ll)k;while((ll)b){if(b&1)--b,(res*=(ll)a)%=mod;b>>=1,(a*=a)%=mod;}return res;}
template<typename T>istream&operator>>(istream&is,vector<T>&vec){for(T&element:vec){is>>element;}return is;}
template<typename T>ostream&operator<<(ostream&os,vector<T>&vec){for(ll i=0;i+1<vec.size();++i){os<<vec[i]<<" ";}if(vec.size()>0)os<<vec.back();return os;}
template<typename T>void chmin(T&x,T y){x=min(x,y);}
template<typename T>void chmax(T&x,T y){x=max(x,y);}
#define fast_io ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define open_files freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout);
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
void solve() {
ll s, n;
cin >> s >> n;
vector<vector<pair<ll, ll>>> by_weight(s + 1);
for (ll i = 0; i < n; ++i) {
ll v, w, k;
cin >> v >> w >> k;
by_weight[w].push_back({v, k});
}
for (ll i = 1; i <= s; ++i) {
sort(rall(by_weight[i]));
}
vector<vector<ll>> newBw(s + 1);
for (ll weight = 1; weight <= s; ++weight) {
ll sizeLimit = s / weight + 1;
for (ll j = 0; j < by_weight[weight].size(); ++j) {
if (newBw[weight].size() >= sizeLimit) break;
while (by_weight[weight][j].second > 0 && newBw[weight].size() < sizeLimit) {
by_weight[weight][j].second--;
newBw[weight].push_back(by_weight[weight][j].first);
}
}
}
vector<ll> knapsack(s + 1, -infll);
knapsack[0] = 0;
for (ll grab = 1; grab <= s; ++grab) {
for (ll v : newBw[grab]) {
for (ll weight = s; weight >= grab; --weight) {
if (knapsack[weight - grab] == -infll) continue;
knapsack[weight] = max(knapsack[weight], knapsack[weight - grab] + v);
}
}
}
cout << *max_element(all(knapsack)) << "\n";
}
signed main() {
fast_io
#ifdef my_dbg
open_files
auto TIME_START = chrono::high_resolution_clock::now();
#endif
cout << fixed << setprecision(25);
solve();
#ifdef my_dbg
auto TIME_FINISH = chrono::high_resolution_clock::now();
auto duration = chrono::duration_cast<std::chrono::nanoseconds>(TIME_FINISH-TIME_START).count();
cerr << "Compiled in: ~";
if (duration / 1e9 < 1) cerr << duration / 1e6 << "ms.\n";
else cerr << duration / 1e9 << "s.\n";
#endif
}
/*
day 1 no lean
author: 160cm
created on: April 07, Friday
*/
