#include <bits/stdc++.h> using namespace std; #define ll long long const ll mmod = 998244353; #define vl vector<long long> #define vll vector<vector<long long>> #define pl pair<long long, long long> #define vb vector<bool> int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); ll n, s; cin >> s >> n; vector<vector<pl>> nums (s+1); for (ll i = 0; i < n; i++){ ll v, w, k; cin >> v >> w >> k; nums[w].push_back({v, k}); } vector<pl> prvky; for (ll i = 1; i <= s; i++){ ll pocet = 0; ll limit = s/i+1; sort(nums[i].begin(), nums[i].end()); reverse(nums[i].begin(), nums[i].end()); for (ll j = 0; j < nums[i].size(); j++){ for (ll k = 0; k < nums[i][j].second; k++){ prvky.push_back({nums[i][j].first, i}); pocet++; if (pocet >= limit){ break; } } if (pocet >= limit){ break; } } } vl dp(s+1, 0); for (ll i = 0; i < prvky.size(); i++){ ll p = prvky[i].first; ll v = prvky[i].second; for (ll j = s; j >= v; j--){ dp[j] = max(dp[j], dp[j-v] + p); } } ll maximum = 0; for (ll i = 0; i < s+1; i++){ maximum = max(maximum, dp[i]); } cout << maximum <<"\n"; return 0; }