#include <bits/stdc++.h>
#define ll long long
#define ii pair<ll, ll>
#define ff first
#define ss second
#define pb(x) push_back(x)
#define vii vector<ll>
#define ump unordered_map
#define sz(a) (int)a.size()
#define getbit(i, j) ((i >> j) & 1)
#define addbit(i, j) (i | (1 << j))
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
#define fto(i, a, b, x) for (int i = a; i <= b; i += x)
#define fdto(i, a, b, x) for (int i = a; i >= b; i -= x)
#define all(x) x.begin(), x.end()
using namespace std;
const ll maxN = 1e5+5;
const ll INF = 1e18;
int S, n;
ll v[maxN], w[maxN], k[maxN];
vector<ll> f;
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> S >> n;
fto (i, 1, n, 1) {
cin >> v[i] >> w[i] >> k[i];
}
f.assign(S+2, 0);
fto (i, 1, S, 1) f[i] = -INF;
fto (i, 1, n, 1) {
vector<multiset<ll>> st(w[i]+1);
vector<queue<int>> q(w[i]+1);
vector<ll> g = f;
fto (weight, 0, S, 1) {
int ww = weight%w[i];
if (st[ww].size()) {
auto j = prev(st[ww].end());
f[weight] = max(f[weight], (*j) + v[i] * (weight / w[i]));
}
st[ww].insert(g[weight] - v[i] * (weight / w[i]));
q[ww].push(weight);
while (st[ww].size() > k[i]) {
int tt = q[ww].front();
q[ww].pop();
st[ww].erase(st[ww].find(g[tt] - v[i] * (tt / w[i])));
}
}
}
ll ans = 0;
// fto (i, 0, S, 1) cout << f[i] << '\n';
fto (i, 0, S, 1) ans = max(ans, f[i]);
cout << ans << '\n';
return 0;
}
