#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].push_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 [value, count] : items[w]) { for (int take = 1; count > 0; take <<= 1) { int used = min(take, count); count -= used; int totalWeight = used * w; ll totalValue = 1LL * used * value; for (int j = S; j >= totalWeight; --j) { dp[j] = max(dp[j], dp[j - totalWeight] + totalValue); } } } } cout << dp[S] << '\n'; return 0; }