#include <bits/stdc++.h> // solved by bekagg #define int long long #define ent '\n' #define pb push_back #define all(x) x.begin(),x.end() #define PRaim_bek_abi ios_base::sync_with_stdio(0);cin.tie(0); using namespace std; const int N = 1e5+5; const int MOD = 1e9+7; int n , s , v[N] , w[N] , k[N]; int dp[N]; void arkanefury228(){ cin >> s >> n; for (int i = 1; i <= n; i++){ cin >> v[i] >> w[i] >> k[i]; k[i] = min(k[i] , s); } for (int i = 1; i <= n; i++){ for (int cnt = 1; cnt <= k[i]; cnt++){ for (int j = s; j >= cnt * w[i]; j--){ dp[j] = max(dp[j] , dp[j - w[i]] + v[i]); } } } int ans = 0; for (int i = 1; i <= s; i++) ans = max(ans , dp[i]); cout << ans; } signed main(){ PRaim_bek_abi int t=1; //cin>>t; for (int respagold = 1; respagold <= t; respagold++) arkanefury228(); }