#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
const ll NEG_INF = -(1LL << 60);
int S, N;
if (!(cin >> S >> N))
return 0;
struct Item {
int v, w;
long long k;
};
vector<Item> items;
items.reserve(N);
for (int i = 0; i < N; ++i) {
int v, w;
long long k;
cin >> v >> w >> k;
if (w <= S && k > 0)
items.push_back({v, w, k});
// else skip: weight too large to ever pick even one copy
}
// dp[pos] = best value achievable with total weight exactly pos
vector<ll> dp(S + 1, NEG_INF);
dp[0] = 0;
// Process each item type with monotonic-queue optimization
for (const auto &it : items) {
int v = it.v;
int w = it.w;
long long k = it.k;
// copy current dp to prev (reads are from prev; writes to dp)
auto prev = dp;
// process residues modulo w
for (int r = 0; r < w; ++r) {
// deque stores pairs (j_index, value = prev[pos] - j*v)
deque<pair<int, ll>> dq;
// iterate over positions pos = r + j * w
// j = 0,1,2,... ; pos <= S
int maxJ = (S - r) / w;
for (int j = 0; j <= maxJ; ++j) {
int pos = r + j * w;
// candidate value for x = j (to be pushed)
// val = prev[pos] - j * v (only meaningful if prev[pos] != NEG_INF)
ll cand = NEG_INF;
if (prev[pos] != NEG_INF)
cand = prev[pos] - (ll)j * v;
// push candidate j: maintain deque decreasing by value
if (cand != NEG_INF) {
while (!dq.empty() && dq.back().second <= cand)
dq.pop_back();
dq.emplace_back(j, cand);
}
// pop front if it's outside window [j - k, j]
while (!dq.empty() && dq.front().first < j - k)
dq.pop_front();
// front of deque is best x for current j
if (!dq.empty()) {
ll best = dq.front().second + (ll)j * v;
// take max: maybe we don't take any of this item type (prev[pos]
// already in dp)
dp[pos] = max(dp[pos], best);
}
// else no valid candidate -> dp[pos] remains as is (can't use this item
// type to reach pos)
}
}
}
// answer: maximum dp[pos] for pos in [0..S] (weight ≤ S)
ll ans = 0;
for (int pos = 0; pos <= S; ++pos)
if (dp[pos] > ans)
ans = dp[pos];
cout << ans << '\n';
return 0;
}
