#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int ll
int32_t main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int S, N;
cin >> S >> N;
vector<int> dp(S + 1, 0);
while (N--) {
int v, w, k;
cin >> v >> w >> k;
int cap = S / w;
if (k > cap) {
// unbounded knapsack
for (int j = w; j <= S; ++j) {
int val = dp[j - w] + v;
if (val > dp[j]) dp[j] = val;
}
} else {
// bounded: sliding window DP for each modulo class
for (int r = 0; r < w; ++r) {
deque<pair<int, int>> dq;
for (int m = 0, j = r; j <= S; ++m, j += w) {
int f = dp[j] - m * v;
while (!dq.empty() && dq.back().second <= f)
dq.pop_back();
dq.emplace_back(m, f);
while (!dq.empty() && dq.front().first < m - k)
dq.pop_front();
dp[j] = dq.front().second + m * v;
}
}
}
}
int res = 0;
for (int x : dp) if (x > res) res = x;
cout << res << '\n';
return 0;
}
