#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstring>
#include <climits>
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>;
const int N = 2e3+7, minf = INT_MIN;
int dp[N], cp[N], val[N];
class Compare {
public:
bool operator() (int i, int j) {
return val[i] < val[j];
}
};
using pq = priority_queue<int, vi, Compare>;
pq q[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++) q[j] = pq();
for(int j = 0; j < m+1; j++) {
int r = j%w;
val[j] = ~cp[j]? cp[j] - (j/w)*v: minf;
q[r].push(j);
while(!q[r].empty()) {
int p = q[r].top(), x = (j-p)/w;
if(x > k) q[r].pop(); else {
dp[j] = ~cp[p]? cp[p] + x*v: -1;
break;
}
}
}
}
int ret = 0;
for(int j = 0; j < m+1; j++) ret = max(ret, dp[j]);
cout << ret << "\n";
}
int main() {
fast_io;
solve();
}
