/*
[templates]:
duipai
spjdp
compre
addhis
floor_sum
treedfs
matrix
*/
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx")
#include<bits/stdc++.h>
using namespace std;
#define int long long
//use ll instead of int.
#define f(i, a, b) for(int i = (a); i <= (b); i++)
#define cl(i, n) i.clear(),i.resize(n);
#define endl '\n'
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int inf = 1e9;
//#define cerr if(false)cerr
//#define freopen if(false)freopen
mt19937 rng(time(0));
int rnd(int l, int r) {return rng() % (r-l+1) + l; }
#define watch(x) cerr << (#x) << ' '<<'i'<<'s'<<' ' << x << endl
void pofe(int number, int bitnum) {
string s; f(i, 0, bitnum) {s += char(number & 1) + '0'; number >>= 1; }
reverse(s.begin(), s.end()); cerr << s << endl;
return;
}
template <typename TYP> void cmax(TYP &x, TYP y) {if(x < y) x = y;}
template <typename TYP> void cmin(TYP &x, TYP y) {if(x > y) x = y;}
//调不出来给我对拍！
//use std::array.
vector<pii> t[2020];
int v[100010], w[100010], k[100010];
int dp[2020];
signed main() {
ios::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
//freopen();
//freopen();
//time_t start = clock();
//think twice,code once.
//think once,debug forever.
int s, n; cin >> s >> n;
f(i, 1, n) {
cin >> v[i] >> w[i] >> k[i];
t[w[i]].push_back({v[i], k[i]});
}
f(i, 1, s) sort(t[i].begin(), t[i].end());
f(i, 1, s) dp[i] = -inf;
f(i, 1, s) {
int hi = s / i;
for(pii j : t[i]) {
int vv = j.first, kk = j.second;
while(hi && kk) {
for(int tt = s; tt >= i; tt --) {
cmax(dp[tt], dp[tt - i] + vv);
}
hi --; kk --;
}
}
}
int ans = 0;
f(i, 0, s) cmax(ans, dp[i]);
cout << ans << endl;
//time_t finish = clock();
//cout << "time used:" << (finish-start) * 1.0 / CLOCKS_PER_SEC <<"s"<< endl;
return 0;
}
