#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll NEG = LLONG_MIN / 4;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int S, N;
if (!(cin >> S >> N)) return 0;
vector<ll> dp(S + 1, NEG);
dp[0] = 0;
for (int i = 0; i < N; ++i) {
int v, w, c;
cin >> v >> w >> c;
// If unlimited (or enough copies to treat as complete knapsack)
if ((long long)w * c >= S) {
for (int j = w; j <= S; ++j) {
if (dp[j - w] != NEG)
dp[j] = max(dp[j], dp[j - w] + v);
}
continue;
}
// Bounded case: process by residues modulo w
for (int r = 0; r < w; ++r) {
// collect original values for indices idx = r + k*w
int maxk = (S - r) / w;
if (maxk < 0) continue;
vector<ll> vals(maxk + 1);
for (int k = 0; k <= maxk; ++k) {
vals[k] = dp[r + k * w]; // original value for this residue
}
deque<int> q; // store k indices
for (int k = 0; k <= maxk; ++k) {
ll cur = vals[k] - (ll)k * v; // value used for queue comparisons
while (!q.empty() && (vals[q.back()] - (ll)q.back() * v) <= cur) q.pop_back();
q.push_back(k);
// drop too-old elements (more than c copies)
while (!q.empty() && q.front() < k - c) q.pop_front();
int best = q.front();
if (vals[best] != NEG) {
// candidate = vals[best] + (k - best) * v
dp[r + k * w] = max(dp[r + k * w], vals[best] + (ll)(k - best) * v);
}
}
}
}
// if dp[S] may be NEG meaning unreachable, you might want to print something else
cout << (dp[S] == NEG ? 0LL : dp[S]) << '\n';
return 0;
}
