#include "bits/stdc++.h" using namespace std; #define rep(i,a,b) for(int i=(a); i<(b); ++i) #define all(x) x.begin(),x.end() #define sz(x) int(x.size()) typedef long long ll; typedef unsigned long long ull; typedef vector<int> vi; typedef vector<vi> vvi; typedef long double T; // long double, Rational, double + mod<P>... typedef vector<T> vd; typedef vector<vd> vvd; const T eps = 1e-8, inf = 1/.0; #define MP make_pair #define ltj(X) if(s == -1 || MP(X[j],N[j]) < MP(X[s],N[s])) s=j struct LPSolver { int m, n; vi N, B; vvd D; LPSolver(const vvd& A, const vd& b, const vd& c) : m(sz(b)), n(sz(c)), N(n+1), B(m), D(m+2, vd(n+2)) { rep(i,0,m) rep(j,0,n) D[i][j] = A[i][j]; rep(i,0,m) { B[i] = n+i; D[i][n] = -1; D[i][n+1] = b[i];} rep(j,0,n) { N[j] = j; D[m][j] = -c[j]; } N[n] = -1; D[m+1][n] = 1; } void pivot(int r, int s) { T *a = D[r].data(), inv = 1 / a[s]; rep(i,0,m+2) if (i != r && abs(D[i][s]) > eps) { T *b = D[i].data(), inv2 = b[s] * inv; rep(j,0,n+2) b[j] -= a[j] * inv2; b[s] = a[s] * inv2; } rep(j,0,n+2) if (j != s) D[r][j] *= inv; rep(i,0,m+2) if (i != r) D[i][s] *= -inv; D[r][s] = inv; swap(B[r], N[s]); } bool simplex(int phase) { int x = m + phase - 1; for (;;) { int s = -1; rep(j,0,n+1) if (N[j] != -phase) ltj(D[x]); if (D[x][s] >= -eps) return true; int r = -1; rep(i,0,m) { if (D[i][s] <= eps) continue; if (r == -1 || MP(D[i][n+1] / D[i][s], B[i]) < MP(D[r][n+1] / D[r][s], B[r])) r = i; } if (r == -1) return false; pivot(r, s); } } T solve(vd &x) { int r = 0; rep(i,1,m) if (D[i][n+1] < D[r][n+1]) r = i; if (D[r][n+1] < -eps) { pivot(r, n); if (!simplex(2) || D[m+1][n+1] < -eps) return -inf; rep(i,0,m) if (B[i] == -1) { int s = 0; rep(j,1,n+1) ltj(D[i]); pivot(i, s); } } bool ok = simplex(1); x = vd(n); rep(i,0,m) if (B[i] < n) x[B[i]] = D[i][n+1]; return ok ? D[m][n+1] : inf; } }; struct ILP{ int n, m; vvd A; vd b, c, lo, hi; T ans = -inf; ILP(vvd A, vd b, vd c) : n(sz(b)), m(sz(c)), A(A), b(b), c(c), lo(m), hi(m,inf) { } void solve(){ T bal = 0; rep(i,0,m) { bal += c[i]*lo[i]; rep(j,0,n) b[j] -= A[j][i]*lo[i]; if (hi[i] < inf){ vd e(m); e[i] = 1; A.push_back(e); b.push_back(hi[i]-lo[i]); } } LPSolver lp(A, b, c); vd x(m), sm(n); T res = floor(bal + lp.solve(x) + .1), me = bal; A.resize(n), b.resize(n); pair<T, pair<ll,ll>> w = {}; rep(i,0,m){ T r = floor(x[i] + eps), d = x[i] - r; w = max(w,{min(d,1-d),{i,r}}), me += r * c[i]; rep(j,0,n) d = A[j][i] * lo[i], b[j] += d, sm[j] += r * A[j][i] + d; } rep(i,0,n) if (sm[i] > b[i]) me = -inf; ans = max(ans, me); if (res > ans and w.first > eps) { auto [i,v] = w.second; T mx = hi[i]; hi[i] = lo[i] + v, solve(); hi[i] = mx, lo[i] += v + 1, solve(); lo[i] -= v + 1; } } }; int main(){ cin.tie(NULL),ios::sync_with_stdio(false); int s; cin >> s; int n; cin >> n; vvd A(1,vd(n)); vd b(1,s); vd c(n); vi cnts(n); rep(i,0,n){ int v,w,k; cin >> v >> w >> k; c[i] = v; A[0][i] = w; cnts[i] = k; } ILP ilp(A,b,c); rep(i,0,n) ilp.hi[i] = cnts[i]; ilp.solve(); cout << llround(ilp.ans) << '\n'; }