#include <bits/stdc++.h> using namespace std; #define int long long #define N 500005 int tc = 1, n, a[N], S, v[N], w[N], k[N], mx, pos[N]; vector <int> dp; int32_t main() { ios::sync_with_stdio(0);cin.tie(0); cin >> S >> n; for(int i = 1; i <= n; i++) { cin >> v[i] >> w[i] >> k[i]; } dp.assign(S + 1, 0); for(int i = 1; i <= n; i++) { for(int j = S; j >= 0; j--) { int sum = 0, cost = 0, l = k[i]; while(l > 0 && j + sum + w[i] <= S) { sum += w[i]; cost += v[i]; l--; dp[j + sum] = max(dp[j + sum], dp[j] + cost); } } } for(int i = 0; i <= S; i++) { mx = max(mx, dp[i]); } cout << mx << '\n'; return 0; }