#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <x86intrin.h>
#include <bits/stdc++.h>
using namespace std;
using str = string;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
template<class T>
using pr = pair<T, T>;
template<class T>
using vt = vector<T>;
template<class T>
using vvt = vector<vt<T>>;
#define ar array
#define pb push_back
#define ff first
#define umap unordered_map
#define ss second
#define all(c) (c).begin(), (c).end()
#define len(x) (int)(x).size()
#define elif else if
#define def function
#define mset multiset
#define uset unordered_set
#define umap unordered_map
#define ube upper_bound
#define lbe lower_bound
#define pq priority_queue
#define F_OR(i, a, b, s) for (int i=(a); (s)>0?i<(b):i>(b); i+=(s))
#define F_OR1(e) F_OR(i, 0, e, 1)
#define F_OR2(i, e) F_OR(i, 0, e, 1)
#define F_OR3(i, b, e) F_OR(i, b, e, 1)
#define F_OR4(i, b, e, s) F_OR(i, b, e, s)
#define GET5(a, b, c, d, e, ...) e
#define F_ORC(...) GET5(__VA_ARGS__, F_OR4, F_OR3, F_OR2, F_OR1)
#define rep(...) F_ORC(__VA_ARGS__)(__VA_ARGS__)
#define each(x, a) for (auto& x: a)
#define r_each(x,a) for(auto& x:a | views::reverse)
template<class T>
constexpr T inf = 0;
template<>
constexpr int inf<int> = 1'000'000'005;
template<>
constexpr long long inf<long long> = (long long) (inf<int>) * inf<int> * 2;
template<>
constexpr unsigned int inf<unsigned int> = inf<int>;
template<>
constexpr unsigned long long inf<unsigned long long> = inf<long long>;
template<>
constexpr __int128 inf<__int128> = __int128(inf<long long>) * inf<long long>;
template<>
constexpr double inf<double> = inf<long long>;
template<>
constexpr long double inf<long double> = inf<long long>;
template<class T, class S>
inline bool ctmax(T &a, const S &b) { return (a < b ? a = b, 1 : 0); }
template<class T, class S>
inline bool ctmin(T &a, const S &b) { return (a > b ? a = b, 1 : 0); }
template<typename T, typename U>
ostream &operator<<(ostream &os, const pair<T, U> &p) {os << p.first << " " << p.second;return os;}
template<typename T, typename U>
istream &operator>>(istream &is, pair<T, U> &p) {is >> p.first >> p.second;return is;}
template<typename T>
ostream &operator<<(ostream &os, const vector<T> &v) {int s = (int) v.size();for (int i = 0; i < s; i++) os << (i ? " " : "") << v[i];return os;}
template<typename T>
istream &operator>>(istream &is, vector<T> &v) {for (auto &x: v) is >> x;return is;}
void read() {}
template<typename T, class... U>
void read(T &t, U &...u) {cin >> t;read(u...);}
void print() { cout << "\n"; }
template<typename T, class... U, char sep = ' '>
void print(const T &t, const U &...u) {cout << t;if (sizeof...(u)) cout << sep;print(u...);}
void write() { cout << " "; }
template<typename T, class... U, char sep = ' '>
void write(const T &t, const U &...u) {cout << t;if (sizeof...(u)) cout << sep;write(u...);}
#define Int(...) \
int __VA_ARGS__; \
read(__VA_ARGS__)
#define Ll(...) \
long long __VA_ARGS__; \
read(__VA_ARGS__)
#define Ull(...) \
unsigned long long __VA_ARGS__; \
read(__VA_ARGS__)
#define Ld(...) \
long double __VA_ARGS__; \
read(__VA_ARGS__)
#define Str(...) \
string __VA_ARGS__; \
read(__VA_ARGS__)
#define Vt(type, name, size) \
vector<type> name(size); \
read(name)
#define Die(...) \
do { \
print(__VA_ARGS__); \
return; \
} while (0)
__attribute__((target("popcnt"))) inline int popcnt(const ull &a) {
return _mm_popcnt_u64(a);
}
inline int lsb(const ull &a) { return a ? __builtin_ctzll(a) : 64; }
inline int ctz(const ull &a) { return a ? __builtin_ctzll(a) : 64; }
inline int msb(const ull &a) { return a ? 63 - __builtin_clzll(a) : -1; }
template<typename T>
inline int gbit(const T &a, int i) {
return (a >> i) & 1;
}
template<typename T>
inline void sbit(T &a, int i, bool b) {
if (gbit(a, i) != b) a ^= T(1) << i;
}
constexpr long long Pw(int n) { return 1LL << n; }
constexpr long long Msk(int n) { return (1LL << n) - 1; }
template<typename T>
vector<int> argsort(const vector<T> &A) {
vector<int> ids((int) A.size());
iota(ids.begin(), ids.end(), 0);
sort(ids.begin(), ids.end(),
[&](int i, int j) { return (A[i] == A[j] ? i < j : A[i] < A[j]); });
return ids;
}
void dusaco(string s) {
ios_base::sync_with_stdio(0); cin.tie(0);
freopen((s+".in").c_str(),"r",stdin);
freopen((s+".out").c_str(),"w",stdout);
}
#define fastio ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);
#define testct Int(t_ct);while(t_ct--)
namespace dbg{
// DEBUG BEGIN
#ifndef ONLINE_JUDGE
template<class L, class R> ostream &operator<<(ostream &out, const pair<L, R> &p){
return out << "{" << p.first << ", " << p.second << "}";
}
template<class Tuple, size_t N> struct _tuple_printer{
static ostream &_print(ostream &out, const Tuple &t){ return _tuple_printer<Tuple, N-1>::_print(out, t) << ", " << get<N-1>(t); }
};
template<class Tuple> struct _tuple_printer<Tuple, 1>{
static ostream &_print(ostream &out, const Tuple& t){ return out << get<0>(t); }
};
template<class... Args> ostream &_print_tuple(ostream &out, const tuple<Args...> &t){
return _tuple_printer<decltype(t), sizeof...(Args)>::_print(out << "{", t) << "}";
}
template<class ...Args> ostream &operator<<(ostream &out, const tuple<Args...> &t){
return _print_tuple(out, t);
}
template<class T> ostream &operator<<(class enable_if<!is_same<T, string>::value, ostream>::type &out, const T &arr){
if(arr.empty()) return out << "{}";
out << "{";
for(auto it = arr.begin(); it != arr.end(); ++ it){
out << *it;
next(it) != arr.end() ? out << ", " : out << "}";
}
return out;
}
ostream &operator<<(ostream &out, const _Bit_reference &bit){
return out << bool(bit);
}
template<class T, class A, class C>
ostream &operator<<(ostream &out, priority_queue<T, A, C> pq){
vector<T> a;
while(!pq.empty()) a.push_back(pq.top()), pq.pop();
return out << a;
}
template<class Head>
void debug_out(Head H){ cerr << H << endl; }
template<class Head, class... Tail>
void debug_out(Head H, Tail... T){ cerr << H << ", ", debug_out(T...); }
void debug2_out(){ }
template<class Head, class... Tail>
void debug2_out(Head H, Tail... T){ cerr << "\n"; for(auto x: H) cerr << x << ",\n"; debug2_out(T...); }
template<class Width, class Head>
void debugbin_out(Width w, Head H){
for(auto rep = w; rep; -- rep, H >>= 1) cerr << (H & 1);
cerr << endl;
}
template<class Width, class Head, class... Tail>
void debugbin_out(Width w, Head H, Tail... T){
for(auto rep = w; rep; -- rep, H >>= 1) cerr << (H & 1);
cerr << ", "; debugbin_out(w, T...);
}
enum CODE{ CCRED = 31, CCGREEN = 32, CCYELLOW = 33, CCBLUE = 34, CCDEFAULT = 39 };
#define debug_endl() cerr << endl
#define debug(...) cerr << "\033[" << (int)CODE(CCRED) << "m[" << #__VA_ARGS__ << "]: \033[" << (int)CODE(CCBLUE) << "m", debug_out(__VA_ARGS__), cerr << "\33[" << (int)CODE(CCDEFAULT) << "m"
#define debug2(...) cerr << "\033[" << (int)CODE(CCRED) << "m[" << #__VA_ARGS__ << "] \033[" << (int)CODE(CCBLUE) << "m", debug2_out(__VA_ARGS__), cerr << "\33[" << (int)CODE(CCDEFAULT) << "m"
#define debugbin(...) cerr << "\033[" << (int)CODE(CCRED) << "m[" << #__VA_ARGS__ << "] \033[" << (int)CODE(CCBLUE) << "m", debugbin_out(__VA_ARGS__), cerr << "\33[" << (int)CODE(CCDEFAULT) << "m"
#else
#define debug_endl() 42
#define debug(...) 42
#define debug2(...) 42
#define debugbin(...) 42
#endif
// DEBUG END
} using namespace dbg;
// Integer factorization in O(N^{1/4}
// uses squfof from msieve https://github.com/radii/msieve
// with fixes to work for n = p^3
// works up to 10^18
// probably fails on 5003^5 which is ~10^{18.5}
namespace Factor {
template<typename T, typename SFINAE = void> struct bigger_type{};
template<typename T> using bigger_type_t = typename bigger_type<T>::type;
template<typename T> struct bigger_type<T, typename enable_if<is_integral<T>::value && is_signed<T>::value && sizeof(T) == 4>::type>{using type = long long;};
template<typename T> struct bigger_type<T, typename enable_if<is_integral<T>::value && !is_signed<T>::value && sizeof(T) == 4>::type>{using type = unsigned long long;};
template<typename T> struct bigger_type<T, typename enable_if<is_integral<T>::value && is_signed<T>::value && sizeof(T) == 8>::type>{using type = __int128;};
template<typename T> struct bigger_type<T, typename enable_if<is_integral<T>::value && !is_signed<T>::value && sizeof(T) == 8>::type>{using type = unsigned __int128;};
template<typename int_t = unsigned long long>
struct Mod_Int{
static inline int_t add(int_t const&a, int_t const&b, int_t const&mod){
int_t ret = a+b;
if(ret>=mod) ret-=mod;
return ret;
}
static inline int_t sub(int_t const&a, int_t const&b, int_t const&mod){
return add(a, mod-b);
}
static inline int_t mul(int_t const&a, int_t const&b, int_t const&mod){
return a*static_cast<bigger_type_t<int_t>>(b)%mod;
}
static inline int_t pow(int_t const&a, int_t const&b, int_t const&mod){
int_t ret = 1;
int_t base = a;
for(int i=0;b>>i;++i){
if((b>>i)&1) ret = mul(ret, base, mod);
base = mul(base, base, mod);
}
return ret;
}
};
template<typename T>
bool is_prime(T x){
static_assert(is_integral<T>::value);
if(x<T(4)) return x>T(1);
for(T i=2;i*i<=x;++i){
if(x%i == 0) return false;
}
return true;
}
template<typename T>
bool miller_rabin_single(T const&x, T base){
static_assert(is_integral<T>::value);
if(x<T(4)) return x>T(1);
if(x%2 == 0) return false;
base%=x;
if(base == 0) return true;
T xm1 = x-1;
int j = 1;
T d = xm1/2;
while(d%2 == 0){ // could use __builtin_ctz
d/=2;
++j;
}
T t = Mod_Int<T>::pow(base, d, x);
if(t==T(1) || t==T(xm1)) return true;
for(int k=1;k<j;++k){
t = Mod_Int<T>::mul(t, t, x);
if(t == xm1) return true;
if(t<=1) break;
}
return false;
}
template<typename T>
bool miller_rabin_multi(T const&){return true;}
template<typename T, typename... S>
bool miller_rabin_multi(T const&x, T const&base, S const&...bases){
static_assert(is_integral<T>::value);
if(!miller_rabin_single(x, base)) return false;
return miller_rabin_multi(x, bases...);
}
template<typename T>
bool miller_rabin(T const&x){
static_assert(is_integral<T>::value);
if(x < 316349281) return miller_rabin_multi(x, T(11000544), T(31481107));
if(x < 4759123141ull) return miller_rabin_multi(x, T(2), T(7), T(61));
return miller_rabin_multi(x, T(2), T(325), T(9375), T(28178), T(450775), T(9780504), T(1795265022));
}
template<typename T>
T isqrt(T const&x){
static_assert(is_integral<T>::value);
assert(x>=T(0));
T ret = static_cast<T>(sqrtl(x));
while(ret>0 && ret*ret>x) --ret;
while(x-ret*ret>2*ret)
++ret;
return ret;
}
template<typename T>
T icbrt(T const&x){
static_assert(is_integral<T>::value);
assert(x>=T(0));
T ret = static_cast<T>(cbrt(x));
while(ret>0 && ret*ret*ret>x) --ret;
while(x-ret*ret*ret>3*ret*(ret+1))
++ret;
return ret;
}
uint64_t isqrt(unsigned __int128 const&x){
unsigned __int128 ret = sqrtl(x);
while(ret>0 && ret*ret>x) --ret;
while(x-ret*ret>2*ret)
++ret;
return ret;
}
vector<uint16_t> saved;
// fast prime factorization from
// https://github.com/radii/msieve
uint64_t squfof_iter_better(uint64_t const&x, uint64_t const&k, uint64_t const&it_max, uint32_t cutoff_div){
if(__gcd((uint64_t)k, x)!=1) return __gcd((uint64_t)k, x);
//cerr << "try: " << x << " " << k << "\n";
saved.clear();
uint64_t scaledn = k*x;
if(scaledn>>62) return 1;
uint32_t sqrtn = isqrt(scaledn);
uint32_t cutoff = isqrt(2*sqrtn)/cutoff_div;
uint32_t q0 = 1;
uint32_t p1 = sqrtn;
uint32_t q1 = scaledn-p1*p1;
if(q1 == 0){
uint64_t factor = __gcd(x, (uint64_t)p1);
return factor==x ? 1:factor;
}
uint32_t multiplier = 2*k;
uint32_t coarse_cutoff = cutoff * multiplier;
//cerr << "at: " << multiplier << "\n";
uint32_t i, j;
uint32_t p0 = 0;
uint32_t sqrtq = 0;
for(i=0;i<it_max;++i){
uint32_t q, bits, tmp;
tmp = sqrtn + p1 - q1;
q = 1;
if (tmp >= q1)
q += tmp / q1;
p0 = q * q1 - p1;
q0 = q0 + (p1 - p0) * q;
if (q1 < coarse_cutoff) {
tmp = q1 / __gcd(q1, multiplier);
if (tmp < cutoff) {
saved.push_back((uint16_t)tmp);
}
}
bits = 0;
tmp = q0;
while(!(tmp & 1)) {
bits++;
tmp >>= 1;
}
if (!(bits & 1) && ((tmp & 7) == 1)) {
sqrtq = (uint32_t)isqrt(q0);
if (sqrtq * sqrtq == q0) {
for(j=0;j<saved.size();++j){
if(saved[j] == sqrtq) break;
}
if(j == saved.size()) break;
//else cerr << "skip " << i << "\n";;
}
}
tmp = sqrtn + p0 - q0;
q = 1;
if (tmp >= q0)
q += tmp / q0;
p1 = q * q0 - p0;
q1 = q1 + (p0 - p1) * q;
if (q0 < coarse_cutoff) {
tmp = q0 / __gcd(q0, multiplier);
if (tmp < cutoff) {
saved.push_back((uint16_t) tmp);
}
}
}
if(sqrtq == 1) { return 1;}
if(i == it_max) { return 1;}
q0 = sqrtq;
p1 = p0 + sqrtq * ((sqrtn - p0) / sqrtq);
q1 = (scaledn - (uint64_t)p1 * (uint64_t)p1) / (uint64_t)q0;
for(j=0;j<it_max;++j) {
uint32_t q, tmp;
tmp = sqrtn + p1 - q1;
q = 1;
if (tmp >= q1)
q += tmp / q1;
p0 = q * q1 - p1;
q0 = q0 + (p1 - p0) * q;
if (p0 == p1) {
q0 = q1;
break;
}
tmp = sqrtn + p0 - q0;
q = 1;
if (tmp >= q0)
q += tmp / q0;
p1 = q * q0 - p0;
q1 = q1 + (p0 - p1) * q;
if (p0 == p1)
break;
}
if(j==it_max) {cerr << "RNG\n"; return 1;} // random fail
uint64_t factor = __gcd((uint64_t)q0, x);
if(factor == x) factor=1;
return factor;
}
uint64_t squfof(uint64_t const&x){
static array<uint32_t, 16> multipliers{1, 3, 5, 7, 11, 3*5, 3*7, 3*11, 5*7, 5*11, 7*11, 3*5*7, 3*5*11, 3*7*11, 5*7*11, 3*5*7*11};
uint64_t cbrt_x = icbrt(x);
if(cbrt_x*cbrt_x*cbrt_x == x) return cbrt_x;
//uint32_t iter_lim = isqrt(isqrt(x))+10;
uint32_t iter_lim = 300;
for(uint32_t iter_fact = 1;iter_fact<20000;iter_fact*=4){
for(uint32_t const&k : multipliers){
if(numeric_limits<uint64_t>::max()/k<=x) continue; //would overflow
uint32_t const it_max = iter_fact*iter_lim;
uint64_t factor = squfof_iter_better(x, k, it_max, 1);
if(factor==1 || factor==x) continue;
return factor;
}
}
cerr << "failed to factor: " << x << "\n";
assert(0);
return 1;
}
template<typename T>
vector<T> factorize(T x){
static_assert(is_integral<T>::value);
vector<T> ret;
const uint32_t trial_limit = 5000;
auto trial = [&](int i){while(x%i == 0){x/=i; ret.push_back(i);}};
trial(2); trial(3);
for(uint32_t i=5, j=2;i<trial_limit && i*i <= x;i+=j, j=6-j){
trial(i);
}
if(x>1){
static stack<T> s;
s.push(x);
while(!s.empty()){
x = s.top(); s.pop();
if(!miller_rabin(x)){
T factor = squfof(x);
if(factor == 1 || factor == x){assert(0); return ret;}
s.push(factor);
s.push(x/factor);
} else {
ret.push_back(x);
}
}
}
sort(ret.begin(), ret.end());
return ret;
}
int64_t euclid_invert(int64_t a, int64_t mod){
a%=mod;
int64_t b = mod, x = 0, x2 = 1, y = 1, y2 = 0, tmp;
while(b){
int64_t q = a / b, r = a % b;
tmp = x;
x = x2 - q * x;
x2 = tmp;
tmp = y;
y = y2 - q * y;
y2 = tmp;
a = b; b = r;
}
if(x2<0) x2+=mod;
return x2;
}
// baby and giant step
int64_t disc_log(int64_t base, int64_t x, int64_t p, int64_t limit){
int64_t block = sqrt(limit);
vector<pair<int64_t, int> > small;
int64_t a = 1;
for(int i=0;i<block;++i){
small.emplace_back(a, i);
a = Mod_Int<int64_t>::mul(a, base, p);
}
sort(small.begin(), small.end());
int64_t big_base = euclid_invert(a, p);
a = x;
for(int j=0;;++j){
auto it = lower_bound(small.begin(), small.end(), make_pair(a, -1));
if(it != small.end() && it->first == a){
return j*block + it->second;
}
a = Mod_Int<int64_t>::mul(a, big_base, p);
}
assert(0);
return 0;
}
// solves x^exp = a (mod p)
// exp and p have to be prime
// returns -1 if there is no solution
int64_t root_extraction(int64_t a, int64_t exp, int64_t p){
assert(miller_rabin(exp));
assert(miller_rabin(p));
if(a == 0) return 0;
if(__gcd(exp, p-1) == 1){
int64_t exp_inv = euclid_invert(exp, p-1);
assert((p-1 == 1) || exp_inv * (__int128)exp % (p-1) == 1);
return Mod_Int<int64_t>::pow(a, exp_inv, p);
}
// now exp divides (p-1)
if(Mod_Int<int64_t>::pow(a, (p-1)/exp, p)!=1){
// no solutions
return -1;
}
// find non-redidue
int64_t res = 2;
while(Mod_Int<int64_t>::pow(res, (p-1)/exp, p) == 1) ++res;
int t = 0;
int64_t s = p-1;
while(s%exp == 0){
s/=exp;
++t;
}
int64_t alph = euclid_invert(exp, s);
int64_t A = Mod_Int<int64_t>::pow(res, (p-1)/exp, p);
int64_t B = Mod_Int<int64_t>::pow(a, alph*exp, p);
B = Mod_Int<int64_t>::mul(B, euclid_invert(a, p), p);
int64_t C = Mod_Int<int64_t>::pow(res, s, p);
int64_t h = 1;
for(int i=1;i<t;++i){
int64_t d = Mod_Int<int64_t>::pow(B, Mod_Int<int64_t>::pow(exp, t-1-i, p-1), p);
int64_t j = 0;
if(d!=1){
j = disc_log(A, d, p, exp);
}
B = Mod_Int<int64_t>::mul(B, euclid_invert(Mod_Int<int64_t>::pow(C, Mod_Int<int64_t>::mul(exp, j, p-1), p), p), p);
h = Mod_Int<int64_t>::mul(h, euclid_invert(Mod_Int<int64_t>::pow(C, j, p), p), p);
C = Mod_Int<int64_t>::pow(C, exp, p);
}
int64_t ret = Mod_Int<int64_t>::mul(Mod_Int<int64_t>::pow(a, alph, p), h, p);
return ret;
}
}
void solve(){
Ll(s,n);
vvt<pr<ll>> w(s+5);
rep(n){
Ll(v,we,k);
w[we].pb({v,k});
}
debug(w);
vt<pr<ll>> v;
rep(s+2){
if(w[i].empty()) continue;
sort(all(w[i]));
ll ct=(s+i-1)/i;
for(;w[i].size() && ct--;){
w[i].back().ss--;
v.pb({i,w[i].back().ff});
if(!w[i].back().ss) w[i].pop_back();
}
}
vt<ll> dp(s+10,0);
dp[0]=0;
rep(v.size()){
rep(j,s+5,v[i].ff,-1){
ctmax(dp[j],dp[j-v[i].ff]+v[i].ss);
}
}
ll res=0;
rep(s+1) ctmax(res,dp[i]);print(res);
}
int main(){
fastio
solve();
}
