#include <iostream> #include <vector> #include <algorithm> #include <deque> using namespace std; void solve() { int S, N; if (!(cin >> S >> N)) return; vector<long long> dp(S + 1, 0); for (int i = 0; i < N; ++i) { long long v, w, c; if (!(cin >> v >> w >> c)) return; if (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; int max_k = (S - r) / w; for (int k = 0; k <= max_k; ++k) { int idx = r + k * w; long long val = dp[idx] - (long long)k * v; while (!q.empty() && q.back().second <= val) { q.pop_back(); } q.push_back({k, val}); while (!q.empty() && q.front().first < k - c) { q.pop_front(); } dp[idx] = max(dp[idx], q.front().second + (long long)k * v); } } } } cout << dp[S] << endl; } int main() { solve(); return 0; }