#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int S, N;
cin >> S >> N;
vector<int> val(N + 1), w(N + 1);
vector<ll> k(N + 1);
for (int i = 1; i <= N; i++) cin >> val[i] >> w[i] >> k[i];
vector<ll> dp(S + 1, 0);
for (int i = 1; i <= N; i++) {
int weight = w[i];
int value = val[i];
ll maxCopies = k[i];
// Split dp by modulo groups
for (int r = 0; r < weight; r++) {
deque<pair<ll, int>> dq; // {dp value - count*value, index}
// iterate over positions j = r, r+weight, r+2*weight...
for (int j = r; j <= S; j += weight) {
int idx = j / weight; // number of items
ll val_j = dp[j] - (ll)idx * value;
// Remove out-of-window elements (window size = maxCopies)
while (!dq.empty() && dq.front().second < idx - maxCopies)
dq.pop_front();
// Maintain decreasing order
while (!dq.empty() && dq.back().first <= val_j)
dq.pop_back();
dq.push_back({val_j, idx});
// Update dp[j] using max in the deque
dp[j] = dq.front().first + (ll)idx * value;
}
}
}
cout << dp[S] << "\n";
return 0;
}
