#include <iostream> #include <vector> #include <deque> #include <algorithm> using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int S, N; if (!(cin >> S >> N)) return 0; vector<long long> dp(S + 1, 0); for (int i = 0; i < N; ++i) { int v, w, c; cin >> v >> w >> c; if ((long long)c * w >= S) { for (int j = w; j <= S; ++j) { dp[j] = max(dp[j], dp[j - w] + v); } } else { for (int r = 0; r < w; ++r) { deque<pair<int, long long>> q; for (int k = 0; k * w + r <= S; ++k) { int idx = k * w + r; long long val = dp[idx] - (long long)k * v; while (!q.empty() && q.back().second <= val) { q.pop_back(); } q.push_back({k, val}); if (q.front().first < k - c) { q.pop_front(); } dp[idx] = max(dp[idx], q.front().second + (long long)k * v); } } } } cout << dp[S] << endl; return 0; }