#include<bits/stdc++.h> #define int long long #define ii pair<int,int> #define fi first #define se second #define getbit(x,y) (((x)>>(y))&1) #define turnon(x,y) ((x)|(1<<y)) #define turnoff(x,y) ((x)^(1<<y)) using namespace std; int s, n; struct shen { int v, w, k; } a[100005]; int cnt[2005]; int dp[2005]; bool cmp(shen x, shen y) { return x.v > y.v; } signed main() { ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin >> s >> n; for (long i = 1; i <= n; i++){ cin >> a[i].v >> a[i].w >> a[i].k; } sort(a+1, a+n+1, cmp); int ans = 0; for (long i = 1; i <= n; i++){ int v = a[i].v, w = a[i].w, k = a[i].k; for (long j = 1; j <= k; j++){ if (cnt[w]*w > s) break; for (long z = s; z >= w; z--){ dp[z] = max(dp[z], dp[z - w] + v); ans = max(ans, dp[z]); } cnt[w]++; } } cout << ans; }