#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int S, N;
if (!(cin >> S >> N)) return 0;
vector<ll> dp(S + 1, 0);
for (int i = 0; i < N; ++i) {
ll v, k;
int w;
cin >> v >> w >> k;
if (w > S) continue; // không nhét nổi 1 cái
ll maxCnt = min(k, (ll)S / w);
if (maxCnt <= 0) continue;
// 1) Nếu k*w >= S: coi như unbounded knapsack
if (maxCnt * w >= S) {
for (int cap = w; cap <= S; ++cap) {
dp[cap] = max(dp[cap], dp[cap - w] + v);
}
} else {
// 2) Bounded với k nhỏ: dùng monotone queue
vector<ll> old = dp; // dp_old
for (int r = 0; r < w; ++r) {
deque<pair<int,ll>> dq; // {index j, value f(j)}
int j = 0;
for (int pos = r; pos <= S; pos += w, ++j) {
ll cur = old[pos] - 1LL * j * v;
// thêm f(j) vào deque, giữ giảm dần theo value
while (!dq.empty() && dq.back().second <= cur)
dq.pop_back();
dq.emplace_back(j, cur);
// cửa sổ chỉ giữ j' >= j - maxCnt
while (!dq.empty() && dq.front().first < j - (int)maxCnt)
dq.pop_front();
dp[pos] = dq.front().second + 1LL * j * v;
}
}
}
}
cout << dp[S] << '\n';
return 0;
}
