#include <iostream> #include <string> #include <vector> #include <cmath> #include <unordered_set> #include <unordered_map> #include <set> #include <algorithm> #include <cctype> #include <limits> #include <iomanip> #include <stack> #include <numeric> #include <map> #include <queue> #include <cfloat> #include <climits> using namespace std; using ll = long long; using ull = unsigned long long; const ll MOD = 1e9 + 7; const ll MAX_SAFE_LL = 1e18; const ll INF = 1e9; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int S, N; cin >> S >> N; vector<vector<pair<int,int>>> items(S + 1); for(int i = 0; i < N; ++i) { int V, W, K; cin >> V >> W >> K; if(W > S) continue; K = min(K, S / W); items[W].emplace_back(V, K); } vector<ll> dp(S + 1, 0); for(int w = 1; w <= S; ++w) { if(items[w].empty()) continue; sort(items[w].rbegin(), items[w].rend()); for(auto [V, K] : items[w]) { for(int j = S; j >= w; --j) { int take = min(K, j / w); for(int k = 1; k <= take; ++k) { dp[j] = max(dp[j], dp[j - k*w] + 1LL*V*k); } } } } cout << dp[S] << "\n"; return 0; }