#include<bits/stdc++.h>
using namespace std;
#define nl '\n'
int n, m, k, p, q, u, v, w, l, r, x, y, z;
// #define int long long
const int N = 1e3 + 10, inf = 1e9, mod = 998244353;
mt19937_64 randll(chrono::steady_clock::now().time_since_epoch().count());
vector<vector<char>> dp;
void solve (int tc = 1) {
cin >> w >> n;
vector<int> dp(w + 1, -inf);
dp[0] = 0;
for (int _ = 0; _ < n; _++) {
int val, wt, freq;
cin >> val >> wt >> freq;
freq = min(freq, w);
for (int md = 0; md < wt; md++) {
deque<pair<int, int>> q;
for (int i = md; i <= w; i += wt) {
while (!q.empty() and q.front().second < i - wt * freq) q.pop_front();
int oval = dp[i];
if (!q.empty()) {
dp[i] = max(dp[i], (i - q.front().second) / wt * val + q.front().first);
}
while (!q.empty() and q.back().first + (i - q.back().second) / wt * val < oval) q.pop_back();
q.push_back(make_pair(oval, i));
}
}
}
cout << *max_element(dp.begin(), dp.end());
}
#undef int
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
int tc = 1;
// cin >> tc;
// scanf("%d", &tc);
while (tc--) {
solve(tc);
if (tc) cout << nl;
// if (tc) printf("\n");
}
}
