#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef pair<int, int> ii;
const int INF = 0x3f3f3f3f;
const ll INFLL = 0x3f3f3f3f3f3f3f3fll;
#define each(x, s) for (auto& x : s)
#define loop(x) for (int i = 0;i < x;i++)
#define vloop(v, x) for (int v = 0;v < x;v++)
#define iter(a) a.begin(), a.end()
#define riter(a) a.rbegin(), a.rend()
#define endl "\n"
struct maxqueue {
list<ii> q;
int t = 0, head = 0;
int del = 0;
void push(int x) {
while (!q.empty() and q.back().first < x - del) q.pop_back();
q.emplace_back(x - del, t++);
}
void pop() {
head++;
if (!q.empty() and q.front().second < head) q.pop_front();
}
int max() {
return q.empty() ? 0 : q.front().first + del;
}
int size() {
return t - head;
}
void clear() {
head = t = del = 0;
q.clear();
}
};
int main() {
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
int s, n;
cin >> s >> n;
vi vs(n), ws(n), ks(n);
loop(n) cin >> vs[i] >> ws[i] >> ks[i];
vector<vi> dp(2, vi(s + 1, 0));
fill(iter(dp[1]), -1);
vector<maxqueue> qs(2001);
int curr = 1;
loop(n) {
vloop(j, ws[i]) qs[j].clear();
dp[curr][0] = 0;
qs[0].push(0);
qs[0].del += vs[i];
for (int j = 1, k = 1 % ws[i];j <= s;j++, k = (k + 1 == ws[i] ? 0 : k + 1)) {
qs[k].push(dp[curr ^ 1][j]);
dp[curr][j] = qs[k].max();
qs[k].del += vs[i];
if (qs[k].size() > ks[i]) qs[k].pop();
}
curr ^= 1;
}
cout << dp[curr ^ 1][s] << endl;
return 0;
}
