#include <iostream>
#include <vector>
#include <algorithm>
#include <deque>
using namespace std;
// Maximum capacity S is 2000
const int mxS = 2000;
// We use long long for DP array to prevent overflow and handle -1e18
long long dp[mxS + 1];
// Structure for the item: Value, Weight, Quantity
struct Item {
long long v, w, k;
};
int main() {
// Fast I/O
ios::sync_with_stdio(0);
cin.tie(0);
int s, n;
cin >> s >> n;
vector<Item> items(n);
for (int i = 0; i < n; i++) {
// Read value, weight, quantity
cin >> items[i].v >> items[i].w >> items[i].k;
}
// Initialize DP array: dp[j] is the max value for capacity j.
// Use a very small number for unreachable states.
fill(dp, dp + mxS + 1, -1e18);
dp[0] = 0;
long long ans = 0;
// --- Start Monotonic Queue Optimized Bounded Knapsack ---
for (const auto& item : items) {
long long v = item.v;
long long w = item.w;
long long k = item.k;
// Iterate over all possible remainders 'r' modulo the item's weight 'w'
for (long long r = 0; r < w && r <= s; r++) {
// Deque stores pairs: {q, f(q)}, where f(q) = dp_old[r + q*w] - q*v
// The deque is maintained to be monotonically decreasing in f(q).
deque<pair<long long, long long>> q;
// Iterate over all capacities j = r + q*w
for (long long j = r; j <= s; j += w) {
long long current_q = (j - r) / w;
// 1. Calculate f(q) for the current capacity j
long long f_q = dp[j] - current_q * v;
// 2. Remove elements from the back that are worse (smaller f(q))
// than the current one (f_q)
while (!q.empty() && q.back().second <= f_q) {
q.pop_back();
}
// Add the current {q, f(q)} to the back
q.push_back({current_q, f_q});
// 3. Remove elements from the front that are outside the sliding window.
// The window size is k. We need max f(q') where q' >= q - k.
if (!q.empty() && q.front().first < current_q - k) {
q.pop_front();
}
// 4. Update the DP state using the maximum value in the queue (q.front().second)
// dp_new[j] = max(f(q')) + q * v
if (!q.empty() && dp[j] != -1e18) { // Only update if a valid state exists
dp[j] = q.front().second + current_q * v;
}
}
}
}
// --- End Monotonic Queue Optimized Bounded Knapsack ---
// Find the overall maximum value
for (int j = 0; j <= s; j++) {
ans = max(ans, dp[j]);
}
cout << ans << endl;
return 0;
}
