// #define gen_test
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
const ld eps = 1e-8;
// for matching the kactl notes
#define sz(x) ((int)x.size())
#define rep(i,a,b) for (int i = (int)(a); i < (int)(b); ++i)
#define all(a) (a).begin(), (a).end()
// #define constexpr(...) (__VA_ARGS__)
// DEBUGING TEMPLETE ////////////////////////////////////////////////////////////////////////{{{
#define db(val) "["#val" = "<<(val)<<"] "
#define CONCAT_(x, y) x##y
#define CONCAT(x, y) CONCAT_(x, y)
#ifdef LOCAL_DEBUG
# define clog cerr << flush << string(__db_level * 2, ' ')
# define DB() debug_block CONCAT(dbbl, __LINE__)
int __db_level = 0;
struct debug_block {
debug_block() { clog << "{" << endl; ++__db_level; }
~debug_block() { --__db_level; clog << "}" << endl; }
};
#else
# define clog if (0) cerr
# define DB(...)
#endif
template<class U, class V> ostream& operator<<(ostream& out, const pair<U, V>& p) {
return out << "(" << p.first << ", " << p.second << ")";
}
template<size_t i, class T> ostream& print_tuple_utils(ostream& out, const T& tup) {
if constexpr(i == tuple_size<T>::value) return out << ")";
else return print_tuple_utils<i + 1, T>(out << (i ? ", " : "(") << get<i>(tup), tup);
}
template<class ...U> ostream& operator<<(ostream& out, const tuple<U...>& tup) {
return print_tuple_utils<0, tuple<U...>>(out, tup);
}
template<class Con, class = decltype(begin(declval<Con>()))>
typename enable_if<!is_same<Con, string>::value, ostream&>::type
operator<<(ostream& out, const Con& container) {
out << "{";
for (auto it = container.begin(); it != container.end(); ++it)
out << (it == container.begin() ? "" : ", ") << *it;
return out << "}";
}
// ACTUAL SOLUTION START HERE ////////////////////////////////////////////////////////////////}}}
const int inf = 21e8;
const int max_s = 2020;
template<class T>
struct StaticDeque {
T data[max_s * 10];
T *head, *tail;
StaticDeque() {
clear();
}
void clear() {
head = tail = data + max_s * 5;
}
size_t size() const {
return tail - head;
}
void push_back(T num) {
*tail++ = num;
}
void pop_back() {
--tail;
}
void pop_front() {
++head;
}
T front() const { return *head; }
T back() const { return tail[-1]; }
};
short mul_board[max_s][max_s];
void precal() {
rep(i, 0, max_s) rep(f, 1, max_s) {
auto x = mul_board[i][f - 1] + i;
mul_board[i][f] = (short)x;
if (x >= max_s) break;
}
}
int get_num() {
int a, c;
while (isspace(a = getchar()));
a -= '0';
while (isdigit(c = getchar())) {
a = a * 10 + c - '0';
}
return a;
}
mt19937 rng;
#define rand() ((int)(rng() >> 1))
int main() {
precal();
#ifdef LOCAL
freopen("main.inp", "r", stdin);
freopen("main.out", "w", stdout);
freopen(".log", "w", stderr);
#endif
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int s, n;
#ifndef gen_test
// cin >> s >> n;
s = get_num(); n = get_num();
#else
s = 2000;
n = 100000;
#endif
vector<int> dp(s + 1, -inf);
dp[0] = 0;
auto new_dp = dp;
while (n--) {
int v;
short w;
int k;
#ifndef gen_test
// cin >> v >> w >> k;
v = get_num(); w = (short)get_num(); k = get_num();
#else
v = rand() % 1000000 + 1;
w = (short)(rand() % s + 1);
k = rand() % ((int)1e9) + 1;
#endif
int div = 0;
for (int i = 1, counter = 1; i <= s; ++i, ++counter) {
if (counter == w) {
div += v;
counter = 0;
}
if (dp[i] >= 0) dp[i] -= div;
new_dp[i] = div;
}
if (k > s / w) {
// if (false) {
rep(rem, 0, w) {
int cur_max = -inf;
for (int i = 0, u = rem; u <= s; ++i, u += w) {
cur_max = max(cur_max, dp[u]);
if (cur_max == -inf) new_dp[u] = -inf;
else new_dp[u] += cur_max;
}
}
} else {
auto& mul_w = mul_board[w];
rep(rem, 0, w) {
static StaticDeque<short> qu;
qu.clear();
auto cur_dp = dp.data() + rem;
for (int i = 0, u = rem; u <= s; ++i, u += w) {
while (qu.size() and i - qu.front() > k) qu.pop_front();
while (qu.size() and (cur_dp[mul_w[qu.back()]] <= dp[u])) qu.pop_back();
qu.push_back((short)i);
int x = cur_dp[mul_w[qu.front()]];
if (x == -inf) new_dp[u] = -inf;
else new_dp[u] += x;
}
}
}
dp = new_dp;
}
cout << *max_element(all(dp));
return 0;
}
// vim: foldmethod=marker
