#include <bits/stdc++.h> using namespace std; template<class T> using V = vector<T>; using ll = long long; using ull = unsigned long long; using ld = long double; using pii = pair<int,int>; using pll = pair<ll,ll>; using vi = V<int>; using vll = V<ll>; #define all(x) begin(x), end(x) #define rall(x) rbegin(x), rend(x) #define sz(x) (int)((x).size()) #define pb push_back #define eb emplace_back #define mp make_pair #define rep(i,n) for (int i = 0; i < (int)(n); ++i) #define rep1(i,n) for (int i = 1; i <= (int)(n); ++i) #define forr(i,a,b) for (int i = (a); i <= (int)(b); ++i) #define rfor(i,a,b) for (int i = (a); i >= (int)(b); --i) const ll INF64 = (1LL<<62) - 1; const int INF = 0x3f3f3f3f; const int MOD = 1'000'000'007; struct FastIO { FastIO() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.setf(std::ios::fixed); cout.precision(12); } } fastio; inline void setIO(const string& inFile, const string& outFile){ if (!inFile.empty()) assert(freopen(inFile.c_str(), "r", stdin) != nullptr); if (!outFile.empty()) assert(freopen(outFile.c_str(), "w", stdout) != nullptr); } inline void setIO(const string& base){ setIO(base + ".in", base + ".out"); } template <class T, class U> struct PairHash { std::size_t operator()(const std::pair<T, U>& p) const noexcept { std::size_t h1 = std::hash<T>{}(p.first); std::size_t h2 = std::hash<U>{}(p.second); return h1 ^ (h2 + 0x9e3779b9 + (h1 << 6) + (h1 >> 2)); } }; template<class T> inline bool chmin(T& a, const T& b){ if(b < a){ a = b; return true; } return false; } template<class T> inline bool chmax(T& a, const T& b){ if(a < b){ a = b; return true; } return false; } template<class T> inline T ceil_div(T a, T b){ return (a>=0 ? (a + b - 1)/b : a/b); } template<class T> inline T floor_div(T a, T b){ return (a>=0 ? a/b : (a - b + 1)/b); } template<class T> inline T clampv(T x, T lo, T hi){ return x < lo ? lo : (x > hi ? hi : x); } template<class T> string to_str(const T& x){ std::ostringstream os; os << x; return os.str(); } template<class T> vector<int> compress(const vector<T>& a, vector<T>* values_out=nullptr){ vector<T> v = a; sort(all(v)); v.erase(unique(all(v)), v.end()); if(values_out) *values_out = v; vector<int> id(a.size()); rep(i, a.size()) id[i] = (int)(lower_bound(all(v), a[i]) - v.begin()); return id; } template<class T> istream& operator>>(istream& is, vector<T>& v){ for (auto& x : v) is >> x; return is; } template<class T> ostream& operator<<(ostream& os, const vector<T>& v){ for (int i = 0; i < sz(v); ++i) os << v[i] << (i+1==sz(v) ? "" : " "); return os; } struct DSU { V<int> e; void init(int N) { e = V<int>(N,-1); } int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); } bool sameSet(int a, int b) { return get(a) == get(b); } int size(int x) { return -e[get(x)]; } bool unite(int x, int y) { x = get(x), y = get(y); if (x == y) return 0; if (e[x] > e[y]) swap(x,y); e[x] += e[y]; e[y] = x; return 1; } }; const int dx4[4] = {1,0,-1,0}, dy4[4] = {0,1,0,-1}; const int dx8[8] = {1,1,0,-1,-1,-1,0,1}, dy8[8] = {0,1,1,1,0,-1,-1,-1}; const int kx[8] = {1,2,2,1,-1,-2,-2,-1}, ky[8] = {2,1,-1,-2,-2,-1,1,2}; int mod = 1000000007; struct item{ double avg; int v, w, k; bool operator<(item other){ return avg < other.avg || (avg == other.avg && w < other.w); } }; int main(){ int S, N; cin >> S >> N; V<item> v; rep(i, N){ int V, W, K; cin >> V >> W >> K; v.pb({V/(double)W, V, W, K}); } sort(rall(v)); //things are commutative, once you hit a weight, you don't need to go to it again, but if you haven't hit it, using all possible copies of current thing is the best move vll dp(S+1, -1); dp[0] = 0; for(auto [avg, value, weight, copies]: v){ //number of copies of current thing required to form some element int c[S+1]{}; for(int i = weight; i <= S; i++){ //thing not reached yet (but thing before possible) and less than max amount of copies used if(dp[i] == -1 && dp[i-weight] != -1 && c[i-weight] < copies){ //best possible way to reach it, never need to recompute this since order by average dp[i] = dp[i-weight]+value; c[i] = c[i-weight]+1; } } //cout << "after [" << avg << ", " << value << ", " << weight << ", " << copies << "], dp = " << dp << endl; } cout << *max_element(all(dp)) << endl; }