#include <bits/stdc++.h> using namespace std; using ll = long long; const int N = 1e5+10, S = 2e4+10; ll dp[S]; vector<pair<ll, ll>> by_w[S]; int main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); int s, n; cin >> s >> n; int sz = 0; for(int i = 1; i <= n; ++i){ ll v, w, k; cin >> v >> w >> k; by_w[w].push_back({v, k}); } for(int i = 1; i <= s; ++i){ sort(by_w[i].begin(), by_w[i].end(), greater<pair<ll, ll>>()); for(auto [v, k] : by_w[i]){ for(int j = 1, took = 0; j <= k && took < s; ++j, took += i){ for(int l = s; l >= 0; --l){ dp[l] = max(dp[l], dp[l-i] + v); } } } } cout << dp[s] << '\n'; }