#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
const int MAXS = 2020;
long long V[MAXN], W[MAXN], K[MAXN];
long long dp[2][MAXS];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int S, n;
cin >> S >> n;
for (int i = 1; i <= n; i++) {
cin >> V[i] >> W[i] >> K[i];
}
int cur = 0;
for (int i = 1; i <= n; i++) {
int weight = W[i];
int value = V[i];
long long maxCopies = K[i];
// Simple deque logic for sliding window max
for (int r = 0; r < weight; r++) {
deque<long long> dq;
// Process positions j = r, r+weight, r+2*weight ...
for (int j = r, idx = 0; j <= S; j += weight, idx++) {
long long val = dp[cur ^ 1][j] - idx * value;
while (!dq.empty() && dq.back() < val) dq.pop_back();
dq.push_back(val);
// Remove elements outside the window of size maxCopies
if (idx > maxCopies) {
long long out = dp[cur ^ 1][j - weight * (maxCopies + 1)] - (idx - maxCopies - 1) * value;
if (dq.front() == out) dq.pop_front();
}
dp[cur][j] = dq.front() + idx * value;
}
}
cur ^= 1; // Switch DP rows
}
cout << dp[cur ^ 1][S] << "\n";
return 0;
}
