#include <bits/stdc++.h> #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); } using namespace std; const int N = 1e5 + 5, M = 2005; int S, n; long long dp[N]; vector<pair<long long, long long>> ve[M], sus; int main() { ios_base::sync_with_stdio(false); cin.tie(0), cout.tie(0); // file("A") else file("task"); cin >> S >> n; for(int i = 1; i <= n; ++i) { int v, w, k; cin >> v >> w >> k; ve[w].emplace_back(v, k); } for(int i = 1; i <= S; ++i) { sort(ve[i].begin(), ve[i].end(), greater<pair<long long, long long>>()); int rem = S / i; for(int j = 0; j < (int)ve[i].size() && rem > 0; ++j) { int sel = min((long long)rem, ve[i][j].second); rem -= sel; while(sel--) sus.emplace_back(ve[i][j].first, i); } } for(pair<long long, long long> p : sus) { for(int i = S; i >= p.second; --i) { dp[i] = max(dp[i], dp[i - p.second] + p.first); } } cout << dp[S] << '\n'; return 0; }