#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <cstring>
#include <climits>
#include <utility>
#include <stack>
using namespace std;
#define fast_io ios::sync_with_stdio(0), cin.tie(0)
#define pb push_back
#define sz(x) (int)x.size()
#define rng(x) begin(x), end(x)
template <typename T>
using vt = vector<T>;
using vi = vt<int>;
using pi = pair<int, int>;
const int N = 2e3+7, minf = INT_MIN;
int dp[N], cp[N], val[N];
bool cmp(int i, int j) {
return val[i] > val[j];
}
void insert(stack<pi> &s, int x) {
if(s.empty()) s.push({x, x}); else {
auto [_, y] = s.top();
s.push({x, cmp(x, y)? x: y});
}
}
struct list {
stack<pi> l, r;
list(): l(), r() {}
int top() {
assert(size() > 0);
int ret = -1;
if(!l.empty()) {
auto [_, x] = l.top();
ret = x;
}
if(!r.empty()) {
auto [_, x] = r.top();
if(~ret) ret = cmp(ret, x)? ret: x; else
ret = x;
}
return ret;
}
void push(int x) {
insert(r, x);
}
void pop() {
assert(size() > 0);
if(l.empty()) {
while(!r.empty()) {
auto [x, _] = r.top();
r.pop(), insert(l, x);
}
}
l.pop();
}
size_t size() {
return l.size()+r.size();
}
bool empty() {
return size() == 0;
}
};
list s[N];
void solve() {
int m, n; cin >> m >> n;
memset(dp, 0xff, sizeof(dp));
dp[0] = 0;
for(int i = 0; i < n; i++) {
int v, w, k; cin >> v >> w >> k;
memcpy(cp, dp, sizeof(cp));
for(int j = 0; j < w; j++) s[j] = list();
for(int j = 0; j < m+1; j++) {
int r = j%w;
val[j] = ~cp[j]? cp[j] - (j/w)*v: minf;
s[r].push(j);
if(s[r].size() > k+1) s[r].pop();
int p = s[r].top(), x = (j-p)/w;
dp[j] = ~cp[p]? cp[p] + x*v: -1;
}
}
int ret = 0;
for(int j = 0; j < m+1; j++) ret = max(ret, dp[j]);
cout << ret << "\n";
}
int main() {
fast_io;
solve();
}
