#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], dp[100001][2001], mx, pos[N]; 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]; } pos[0] = 1; for(int i = 1; i <= n; i++) { for(int j = 0; j <= S; j++) { dp[i][j] = dp[i - 1][j]; int sum = 0, cost = 0, l = k[i]; while(l--) { sum += w[i]; cost += v[i]; if(sum > j) break; if(pos[j - sum]){ dp[i][j] = max(dp[i][j],dp[i - 1][j - sum] + cost); pos[j] = 1; } } } } for(int i =0;i <= S; i++) { mx = max(mx,dp[n][i]); } cout << mx << '\n'; return 0; }