#include <bits/stdc++.h> #define int long long #define nn '\n' using namespace std; signed main() { int s, n; cin >> s >> n; vector<int> v(n + 1), w(n + 1), k(n + 1); vector<int> dp(s + 1, 0); for (int i = 1; i <= n; i++) { cin >> v[i] >> w[i] >> k[i]; } if (n == 1) { int l = 1, r = k[1]; int ans = 0; while (l <= r) { int mid = (l + r) / 2; if (mid * w[1] <= s) { ans = mid; l = mid + 1; } else { r = mid - 1; } } cout << ans * v[1]; } else { for (int i = 1; i <= n; i++) { int l = 1, r = k[i]; int ans = 0; while (l <= r) { int mid = (l + r) / 2; if (mid * w[i] <= s) { ans = mid; l = mid + 1; } else { r = mid - 1; } } for (int cnt = 1; cnt <= ans; cnt++) { for (int j = s; j >= w[i]; j--) { dp[j] = max(dp[j], dp[j - w[i]] + v[i]); } } } cout << dp[s]; } }