#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); pos[0] = 1; for(int i = 1; i <= n; i++) { vector <int> pd = dp; for(int j = 0; j <= S; 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]){ pd[j] = max(pd[j],dp[j - sum] + cost); pos[j] = 1; } } } dp = pd; } for(int i = 0; i <= S; i++) { mx = max(mx,dp[i]); } cout << mx << '\n'; return 0; }