// #pragma GCC optimize("Ofast") #include <bits/stdc++.h> using namespace std; #define el "\n" #define pii pair<int, int> #define pll pair<ll, ll> #define fi first #define se second #define mp make_pair #define sqr(x) ((x) * (x)) #define FOR(i, l, r) for (int i = l; i <= (r); i++) #define FOD(i, l, r) for (int i = l; i >= (r); i--) #define all(x) begin(x), end(x) #define rall(x) rbegin(x), rend(x) #define sz(x) ((int)(x).size()) #define fast_io ios_base::sync_with_stdio(false); cin.tie(nullptr); using db = long double; using ll = long long; using ull = unsigned long long; using vi = vector<int>; using vll = vector<ll>; using vpii = vector<pii>; using vpll = vector<pll>; using vvi = vector<vi>; using vvll = vector<vll>; using vbool = vector<bool>; using vvbool = vector<vbool>; template<class T> inline bool chmax(T &a, T const &b) { return (a < b ? (a = b, true) : false); } template<class T> inline bool chmin(T &a, T const &b) { return (a > b ? (a = b, true) : false); } // #define DEBUG #ifdef DEBUG #include "D:\cpp\debug.h" #else #define debug(...) #define debug_arr(...) #endif mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count()); constexpr int N = 1E5 + 5, S = 2E3 + 5; constexpr int INF = 1E9 + 7; constexpr ll INFLL = 4E18; constexpr int MOD = 1E9 + 7; // 998244353 constexpr double EPS = 1E-10; int v[N], w[N], k[N]; int cnt[S]; ll dp[S]; int s, n; void solve() { cin >> s >> n; FOR(i, 1, n) { cin >> v[i] >> w[i] >> k[i]; } vi order(n); iota(all(order), 1); sort(all(order), [&](int i, int j) { return v[i] > v[j]; }); for (int i : order) { while (k[i]--) { if (cnt[w[i]] * w[i] > s) break; FOD(j, s, w[i]) { chmax(dp[j], dp[j - w[i]] + v[i]); } cnt[w[i]]++; } } cout << dp[s] << el; } int main() { fast_io #define LOCAL #ifndef LOCAL #define PROBLEM "" freopen(PROBLEM ".INP", "r", stdin); freopen(PROBLEM ".OUT", "w", stdout); #endif int t = 1; // cin >> t; while (t--) solve(); }