#include <bits/stdc++.h> #define ll long long #define pii pair<int, int> using namespace std; const int N = 1e5 + 7; int dp[N]; vector<pii> item[N]; signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int s, n; cin >> s >> n; for (int i = 1; i <= n; i++) { int v, w, k; cin >> v >> w >> k; item[w].push_back({v, k}); } for (int w = 1; w <= s; w++) { sort(item[w].begin(), item[w].end(), greater<pii>()); int sum = 0; for (auto [v, k] : item[w]) { while (sum + w <= s && k) { k--; sum += w; for (int i = s; i >= w; i--) dp[i] = max(dp[i], dp[i - w] + v); } if (sum + w > s) break; } } cout << dp[s] << '\n'; return 0; }