#include<bits/stdc++.h> #define int long long #define pb push_back #define fi first #define se second #define ii pair<int,int> using namespace std; const int maxn = 2005; int n; int s; struct node { int v, w, k; }; node a[maxn]; bool cmp(node a, node b) { return a.v > b.v; } int used[maxn]; int dp[maxn]; signed main(){ ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); // freopen(".inp" , "r" , stdin); // freopen(".out" , "w" , stdout); cin >> s >> n; for(int i = 1; i <= n; i++){ cin >> a[i].v >> a[i].w >> a[i].k; } sort(a + 1, a + n + 1, cmp); memset(dp, -0x3f, sizeof dp); dp[0] = 0; for(int i = 1; i <= n; i++){ for(int sl = 1; sl <= a[i].k; sl++){ if(used[a[i].w] * sl > s) break; for(int sum = s; sum >= a[i].w; sum--){ dp[sum] = max(dp[sum], dp[sum - a[i].w] + a[i].v); } used[a[i].w]++; } } int res = 0; for(int i = 0; i <= s; i++){ // cout << dp[i] << " "; res = max(res, dp[i]); } // cout << "\n"; cout << res << "\n"; }