/** @author Mihari */
#pragma GCC optimize(2)
#include <cstdio>
#include <iostream>
#include <cstring>
// using namespace std;
#define USING_FREAD
#define NDEBUG
#include <cassert>
namespace Mihari {
#define rep(i, l, r) for(int i = (l), i##_end_ = (r); i <= i##_end_; ++i)
#define repf(i, l, r) for (int i = (l), i##_end_ = (r); i < i##_end_; ++i)
#define drep(i, l, r) for(int i = (l), i##_end_ = (r); i >= i##_end_; --i)
#define fi first
#define se second
#define mp(a, b) make_pair(a, b)
#define Endl putchar('\n')
#define whole(v) ((v).begin()), ((v).end())
#define bitcnt(s) (__builtin_popcount(s))
/** @warning no forced type conversion */
#define rqr(x) ((x) * (x))
#define y0 FUCK_UP
#define y1 MOTHER_FUCKER
#define masdf(...) fprintf(stderr, __VA_ARGS__)
typedef long long ll;
typedef unsigned long long ull;
typedef std::pair<int, int> pii;
template<class T> inline T fab(T x) { return x < 0 ? -x : x; }
template<class T> inline void chkmin(T& x, const T rhs) { x = std::min(x, rhs); }
template<class T> inline void chkmax(T& x, const T rhs) { x = std::max(x, rhs); }
#ifdef USING_FREAD
inline char qkgetc() {
# define BUFFERSIZE 1 << 20
static char BUF[BUFFERSIZE], *p1 = BUF, *p2 = BUF;
return p1 == p2 && (p2 = (p1 = BUF) + fread(BUF, 1, BUFFERSIZE, stdin), p1 == p2) ? EOF : *p1++;
# undef BUFFERSIZE
}
# define CHARRECEI qkgetc()
#else
# define CHARRECEI getchar()
#endif
template<class T> inline T readret(T x) {
x = 0; int f = 0; char c;
while (!isdigit(c = CHARRECEI)) if(c == '-') f = 1;
for (x = (c ^ 48); isdigit(c = CHARRECEI); x = (x << 1) + (x << 3) + (c ^ 48));
return f ? -x : x;
}
template<class T> inline void readin(T& x) {
x = 0; int f = 0; char c;
while (!isdigit(c = CHARRECEI)) if (c == '-') f = 1;
for (x = (c ^ 48); isdigit(c = CHARRECEI); x = (x << 1) + (x << 3) + (c ^ 48));
if (f) x = -x;
}
template<class T, class... Args> inline void readin(T& x, Args&... args) {
readin(x), readin(args...);
}
template<class T> inline void writln(T x, char c = '\n') {
if (x < 0) putchar('-'), x = -x;
static int __stk[55], __bit = 0;
do __stk[++__bit] = static_cast<int>(x % 10), x /= 10; while (x);
while (__bit) putchar(__stk[__bit--] ^ 48);
putchar(c);
}
} // namespace Mihari
using namespace Mihari;
const int Maxn = (int)1e5;
const int Maxs = 2000;
int siz, n;
int val[Maxn + 5], wei[Maxn + 5], cnt[Maxn + 5];
inline void input() {
readin(siz, n);
rep (i, 1, n) readin(val[i], wei[i], cnt[i]);
}
int g[Maxs + 5], dp[Maxs + 5];
int q[Maxs + 5], op, ed;
inline void getDp() {
memset(dp, -0x3f, sizeof dp);
dp[0] = 0;
rep (i, 1, n) {
memcpy(g, dp, siz + 1 << 2);
rep (r, 0, wei[i] - 1) {
q[op = ed = 1] = r;
for (int cur = wei[i] + r; cur <= siz; cur += wei[i]) {
while ((cur - q[op]) / wei[i] > cnt[i]) ++op;
chkmax(dp[cur], g[q[op]] + (cur - q[op]) / wei[i] * val[i]);
while (op <= ed && (cur - q[op]) / wei[i] * val[i] < g[cur] - g[q[op]]) ++op;
q[++ed] = cur;
}
}
}
int mxx = -1;
rep (i, 0, siz) chkmax(mxx, dp[i]);
writln(mxx);
}
signed main() {
input();
getDp();
return 0;
}
