/*
Problems:
Author: AkiYuu
*/
#include <bits/stdc++.h>
#define task "GROUP"
#define ll long long
#define ld long double
#define pb(u) emplace_back(u)
#define ffw(i,a,b) for (ll i = a; i <= b; i++)
#define fbw(i,b,a) for (ll i = b; i >= a; i--)
#define adj(v,adj,u) for (auto v : adj[u])
#define rep(i,a) for (auto i : a)
#define reset(a) memset(a, 0, sizeof(a))
#define sz(a) a.size()
#define all(a) a.begin(),a.end()
using namespace std;
inline namespace FastIO {
const int BSZ = 1<<15;
char ibuf[BSZ]; int ipos, ilen;
char nc() { //
if (ipos == ilen) {
ipos = 0; ilen = fread(ibuf,1,BSZ,stdin);
if (!ilen) return EOF;
}
return ibuf[ipos++];
}
void readstr(string& x) {
char ch; while (isspace(ch = nc()));
do { x += ch; } while (!isspace(ch = nc()) && ch != EOF);
}
template<class T> void readnum(T& x){
char ch; int sgn = 1;
while (!isdigit(ch = nc())) if (ch == '-') sgn *= -1;
x = ch-'0'; while (isdigit(ch = nc())) x = x*10+(ch-'0');
x *= sgn;
}
}
void fastio(){
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
// freopen(task".inp", "r", stdin);
// freopen(task".out", "w", stdout);
}
const int mxn = 1e6 + 5;
const ll inf = 1e18 + 7;
typedef pair<ll, ll> ii;
int S , n;
vector < ii > a[mxn];
int dp[mxn];
void solve(){
cin >> S >> n;
ffw(i,1,n){
int v, k, w;
cin >> v >> w >> k;
a[w].pb(ii(v,k));;
}
reset(dp);
ffw(w,1,S){
if (a[w].size() == 0 ) continue;
sort(all(a[w]), greater<ii>() );
int id = 0;
for (int i = w; i <= S && id < sz(a[w]) ; i+=w){
int val = a[w][id].first;
// cout << val << " ";
if ( --a[w][id].second == 0 ) id++;
fbw(j,S,w) dp[j] = max(dp[j], dp[j - w] + val);
}
// cout << '\n';
}
cout << *max_element(dp+1,dp+1+S);
}
int main(){
fastio();
solve();
}
