#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); vector<ll> dp(s + 1); for(int i = 0; i < n; ++i) { int v, w, k; cin >> v >> w >> k; items[w].push_back(make_pair(v, min(s / w, k))); } for(int i = 1; i <= s; ++i) { if(items[i].empty()) continue; sort(items[i].begin(), items[i].end(), greater<pair<int, int>>()); int mx = s; for(auto& pr : items[i]) { while(mx >= i && pr.second) { for(int j = s; j >= i; --j) { dp[j] = max(dp[j], dp[j - i] + pr.first); } pr.second--; mx -= i; } if(mx < i) break; } } cout << dp[s] << '\n'; return 0; }