#include <bits/stdc++.h>
#include <vector>
#include <tuple>
// #include "debugging.h"
// #include <atcoder/lazysegtree>
// #include <atcoder/dsu>
// #include <atcoder/segtree>
// #include <atcoder/modint>
// using namespace atcoder;
// using mint = static_modint<998244353>;
using namespace std;
const int LARGE = 1e9;
#define all(x) (x).begin(), (x).end()
using ll = long long;
typedef pair<ll, ll> pi;
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
struct chash { /// use most bits rather than just the lowest ones
const uint64_t C = ll(4e18 * acos(0)) + 71; // large odd number
const int RANDOM = rng();
ll operator()(ll x) const { return __builtin_bswap64((x ^ RANDOM) * C); }
}; /// https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html
/// template<class K,class V> using um = unordered_map<K,V,chash>;
template <class K, class V>
using ht = gp_hash_table<K, V, chash, equal_to<K>, direct_mask_range_hashing<>,
linear_probe_fn<>,
hash_standard_resize_policy<hash_exponential_size_policy<>,
hash_load_check_resize_trigger<>, true>>;
template <class K, class V>
V get(ht<K, V>& u, K x)
{
auto it = u.find(x);
return it == end(u) ? 0 : it->s;
}
// bool cmp(pair<ll, ll> a, pair<ll, ll> b)
// {
// if (a.second < b.second)
// return true;
// return false;
// }
// struct node
// {
// // part which will store data
// int data;
// // pointer to the previous node
// struct node *prev;
// // pointer to the next node
// struct node *next;
// };
// struct trienode
// {
// vector<trienode*> desc;
// vector<ll> descExist;
// trienode(ll M) {
// desc.resize(M);
// descExist.resize(M);
// }
// };
const int MOD = 998244353;
// template<int MOD, int RT> struct mint {
// static const int mod = MOD;
// static constexpr mint rt() { return RT; } // primitive root
// int v;
// explicit operator int() const { return v; }
// mint():v(0) {}
// mint(ll _v):v(int(_v%MOD)) { v += (v<0)*MOD; }
// mint& operator+=(mint o) {
// if ((v += o.v) >= MOD) v -= MOD;
// return *this; }
// mint& operator-=(mint o) {
// if ((v -= o.v) < 0) v += MOD;
// return *this; }
// mint& operator*=(mint o) {
// v = int((ll)v*o.v%MOD); return *this; }
// friend mint pow(mint a, ll p) { assert(p >= 0);
// return p==0?1:pow(a*a,p/2)*(p&1?a:1); }
// friend mint inv(mint a) { assert(a.v != 0); return pow(a,MOD-2); }
// friend mint operator+(mint a, mint b) { return a += b; }
// friend mint operator-(mint a, mint b) { return a -= b; }
// friend mint operator*(mint a, mint b) { return a *= b; }
// };
// using mi = mint<(int)MOD, 5>;
// struct mySeg
// {
// vector<ll> A;
// ll N;
// void build()
// {
// A.resize(N * 2);
// for (int i = 0; i < N; i++)
// A[i + N] = A[i];
// for (int i = N - 1; i > 0; i--)
// A[i] = min(A[i << 1], A[i << 1 ^ 1]);
// // for (auto el : A) cout << el << " ";
// }
// void set(ll idx, ll val)
// {
// idx += N;
// A[idx] = val;
// for (int i = idx >> 1; i > 0; i >>= 1)
// A[i] = min(A[i << 1], A[i << 1 ^ 1]);
// // for (auto el : A) cout << el << " ";
// }
// ll minnQuery(ll l, ll r)
// {
// ll minn = INT64_MAX;
// for (l = l + N, r = r + N; l < r; l >>= 1, r >>= 1)
// {
// if (l % 2)
// minn = min(minn, A[l++]);
// if (r % 2)
// minn = min(minn, A[--r]);
// }
// return minn;
// }
// };
// template <class T>
// class myFen
// {
// private:
// int N;
// vector<T> A;
// vector<T> BIT;
// public:
// myFen(int size) : N(size), A(size + 1), BIT(size + 1) {}
// void set(ll idx, ll val)
// {
// update(idx, val - A[idx]);
// A[idx] = val;
// }
// void update(ll idx, ll diff)
// {
// for (idx = idx; idx <= N; idx += idx & (-idx))
// BIT[idx] += diff;
// }
// ll sumQuery(ll idx)
// {
// if (idx == 0)
// return 0LL;
// ll summ = 0;
// for (idx = idx; idx > 0; idx -= idx & (-idx))
// summ += BIT[idx];
// return summ;
// }
// };
// mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
// class HashedString {
// private:
// // change M and B if you want
// static const ll M = (1LL << 61) - 1;
// static const ll B;
// // pow[i] contains B^i % M
// static vector<ll> pow;
// // p_hash[i] is the hash of the first i characters of the given string
// vector<ll> p_hash;
// __int128 mul(ll a, ll b) { return (__int128)a * b; }
// ll mod_mul(ll a, ll b) { return mul(a, b) % M; }
// public:
// HashedString(const string &s) : p_hash(s.size() + 1) {
// while (pow.size() < s.size()) { pow.push_back(mod_mul(pow.back(), B)); }
// p_hash[0] = 0;
// for (int i = 0; i < s.size(); i++) {
// p_hash[i + 1] = (mul(p_hash[i], B) + s[i]) % M;
// }
// }
// ll get_hash(int start, int end) {
// ll raw_val = p_hash[end + 1] - mod_mul(p_hash[start], pow[end - start + 1]);
// return (raw_val + M) % M;
// }
// };
// vector<ll> HashedString::pow = {1};
// const ll HashedString::B = uniform_int_distribution<ll>(0, M - 1)(rng);
ll power(ll x, ll y, ll M)
{
if (y == 0)
return ll(1);
ll p = power(x, y / ll(2), M) % M;
p = (p * p) % M;
return (y % ll(2) == 0) ? p : (x * p) % M;
}
int solve()
{
ll S, N; cin >> S >> N;
vector<vector<pair<ll,ll>>> W(S+1);
for (int i = 0; i < N; i++) {
ll v, w, k; cin >> v >> w >> k;
if (w <= S) {
for (int j = 0; j < k; j++) {
W[w].push_back(make_pair(v, k));
}
}
}
vector<vector<ll>> dp(2, vector<ll>(S+1, 0));
ll dpState = 0;
for (int i = 1; i <= S; i++) {
sort(all(W[i]), greater<pair<ll,ll>>());
vector<ll> temp(0);
for (int j = 0; j < W[i].size(); j++) {
for (int k = 0; k < W[i][j].second; k++) {
temp.push_back(W[i][j].first);
if (temp.size() > 2000) break;
}
if (temp.size() > 2000) break;
}
if (temp.size() == 0) continue;
vector<ll> ps(temp.size()+1, 0);
for (int j = 0; j < temp.size(); j++) {
ps[j+1] = ps[j] + temp[j];
}
vector<pair<ll,ll>> dpStItEn(i, make_pair(0,0));
for (int j = 0; j <= S; j++) {
ll currDp = j/i;
ll remIdx = j%i;
while (currDp > dpStItEn[remIdx].first) {
if (ps[min(ll(ps.size()-1), dpStItEn[remIdx].second-1)] + dp[dpState][remIdx+(dpStItEn[remIdx].first+1)*i] >= ps[min(ll(ps.size()-1), dpStItEn[remIdx].second)] + dp[dpState][remIdx+dpStItEn[remIdx].first*i]) {
dpStItEn[remIdx].first++;
dpStItEn[remIdx].second--;
} else {
break;
}
}
dp[dpState^1][j] = max(dp[dpState^1][j], ps[min(ll(ps.size()-1), dpStItEn[remIdx].second)] + dp[dpState][remIdx+dpStItEn[remIdx].first*i]);
dpStItEn[remIdx].second++;
}
dpState ^= 1;
}
ll ans = 0;
for (int i = 0; i <= S; i++) {
ans = max(ans, dp[dpState][i]);
}
cout << ans << '\n';
return 0;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
// freopen("spainting.in", "r", stdin);
// freopen("spainting.out", "w", stdout);
// ll caseCnt = 1;
// ll T;
// cin >> T;
// while (T--)
// {
solve();
// cout << "Case #"<< caseCnt << ": " << ans << '\n';
// caseCnt++;
// }
return 0;
}
