#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int ll
int32_t main() {
ios::sync_with_stdio(false);
cin.tie(0);
int S, N;
cin >> S >> N;
vector<int> dp(S+1, 0);
for (int i = 0; i < N; i++) {
int V, W, K;
cin >> V >> W >> K;
// If effectively unbounded, do classic unbounded knapsack in O(S)
if ((ll)W * K >= S) {
for (int j = W; j <= S; j++) {
dp[j] = max(dp[j], dp[j - W] + V);
}
continue;
}
// Otherwise do bounded knapsack with monotonic‐queue optimization
// Process each residue class r = 0,1,...,W-1
for (int r = 0; r < W; r++) {
deque<pair<int,int>> dq;
// We look at positions j = r + m*W (m=0,1,2,...) up to S
for (int m = 0, j = r; j <= S; m++, j += W) {
// f(m) = dp_prev[j] - m*V
int fm = dp[j] - m * V;
// push new m into deque, maintaining decreasing fm
while (!dq.empty() && dq.back().second <= fm)
dq.pop_back();
dq.emplace_back(m, fm);
// pop front if outside window of size K+1
while (!dq.empty() && dq.front().first < m - K)
dq.pop_front();
// best is dq.front()
dp[j] = dq.front().second + m * V;
}
}
}
// Answer is the maximum over all weights ≤ S
cout << *max_element(dp.begin(), dp.end()) << "\n";
return 0;
}
