#include <bits/stdc++.h> using namespace std; #define int long long #define eb emplace_back #define mp make_pair #define pb push_back #define pp pop_back #define endl '\n' #define ff first #define ss second #define stop exit(0) #define sz(x) (int)x.size() #define pause system("pause") #define all(x) (x).begin(), (x).end() #define deb(x) cout << #x << "-" << x << endl mt19937 mt(time(nullptr)); typedef char chr; typedef string str; typedef long long ll; typedef vector<int> vii; typedef pair<int, int> pii; const long long INF = LLONG_MAX; const int inf = INT_MAX; const int mod = 1000003; const int MOD = 1000000007; const int dx[] = {-1,0,1,0}; const int dy[] = {0,1,0,-1}; const double PI = 2 * acos(0.0); const int N = 1e6+5; int n,s; int v[N],w[N],k[N]; int fix[N],cnt[N]; int dp[N]; inline void test_case() { cin >> s >> n; for (int i = 1; i <= n; i++) { cin >> v[i] >> w[i] >> k[i]; } iota(fix+1,fix+1+n,1); sort(fix+1,fix+1+n,[](int a, int b) { return v[a]>v[b]; }); for (int ii = 1; ii <= n; ii++) { int i = fix[ii]; for (int j = 1; j <= k[i]; j++) { if (cnt[i]*w[i]>s) break; for (int l = s; l >= w[i]; l--) { dp[l] = max(dp[l],dp[l-w[i]]+v[i]); } cnt[w[i]]++; } } int ans = 0; for (int i = 0; i <= s; i++) { ans = max(ans,dp[i]); } cout << ans << endl; } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); int T = 1; // cin >> T; while (T--) test_case(); return 0; }