#include <iostream>
#include <vector>
#include <map>
#include <functional>
#include <cstring>
#include <set>
#include <algorithm>
#include <queue>
#include <numeric>
#include <iomanip>
#include <assert.h>
#include <stack>
#include <limits>
#include <unordered_map>
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <cmath>
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
using namespace std;
using ll = long long;
constexpr ll MOD = 998244353;
constexpr int maxN = 1e6 + 1;
constexpr ll MAXLL = 0x3f3f3f3f3f3f3f3f;
ll binary_exp(ll a, ll b, ll c) {
ll res = 1;
while (b > 0) {
if (b & 1) {
res = ((res % c) * (a % c)) % c;
}
a = ((a % c) * (a % c)) % c;
b >>= 1;
}
return res;
}
ll mod_mul(ll a, ll b, ll mod) {
a%= mod;
b%=mod;
return (a * b) % mod;
}
ll mod_sub(ll a, ll b, ll mod) {
a%= mod;
b%= mod;
a -= b;
while (a < 0) a += mod;
return a;
}
ll mminvprime(ll a, ll p) {
return binary_exp(a, p - 2, p);
}
namespace Trie {
struct BinTrieNode {
std::array<int, 2> children;
int strings_ending_here;
int strings_going_below;
int end;
BinTrieNode() {
children = {-1, -1};
strings_ending_here = 0;
strings_going_below = 0;
end = -1;
}
};
struct BinTrie {
std::vector<BinTrieNode> trieTree;
int sizeOfTrie;
int B;
BinTrie(int bits = 31) : sizeOfTrie(1), B(bits) {
trieTree.push_back(BinTrieNode());
}
static long long full_size(int bit) {
if (bit < 0) return 1;
return 1LL << bit;
}
int subtree_size(int node) const {
return trieTree[node].strings_going_below;
}
bool search(int num) const {
int currNode = 0;
for (int bit = B; bit >= 0; --bit) {
int b = (num >> bit) & 1;
int nxt = trieTree[currNode].children[b];
if (nxt == -1) return false;
currNode = nxt;
}
return trieTree[currNode].strings_ending_here > 0;
}
void add(int num) {
int currNode = 0;
for (int bit = B; bit >= 0; --bit) {
int b = (num >> bit) & 1;
if (trieTree[currNode].children[b] == -1) {
trieTree[currNode].children[b] = sizeOfTrie;
trieTree.push_back(BinTrieNode());
++sizeOfTrie;
}
currNode = trieTree[currNode].children[b];
++trieTree[currNode].strings_going_below;
}
++trieTree[currNode].strings_ending_here;
}
void add_unique(int num) {
if (search(num)) return;
add(num);
}
void remove(int num) {
if (!search(num)) return;
int currNode = 0;
for (int bit = B; bit >= 0; --bit) {
int b = (num >> bit) & 1;
int child = trieTree[currNode].children[b];
--trieTree[child].strings_going_below;
if (trieTree[child].strings_going_below == 0) {
trieTree[currNode].children[b] = -1;
return;
}
currNode = child;
}
--trieTree[currNode].strings_ending_here;
}
int findMaxXor(int num) const {
if (sizeOfTrie <= 1) return -1;
int currNode = 0;
int bestNum = 0;
for (int bit = B; bit >= 0; --bit) {
int currentBit = (num >> bit) & 1;
int targetBit = currentBit ^ 1;
int go = trieTree[currNode].children[targetBit];
if (go != -1) {
currNode = go;
if (targetBit) bestNum |= (1U << bit);
} else {
currNode = trieTree[currNode].children[currentBit];
if (currentBit) bestNum |= (1U << bit);
}
}
return bestNum;
}
int mex_after_xor(int cur) const {
int node = 0;
int y = 0;
for (int bit = B; bit >= 0; --bit) {
int cb = (cur >> bit) & 1;
int prefer = cb;
int other = cb ^ 1;
int nxt = trieTree[node].children[prefer];
if (nxt == -1) {
return y;
}
long long cap = full_size(bit);
if ((long long)trieTree[nxt].strings_going_below < cap) {
node = nxt;
} else {
y |= (int)(1U << bit);
int nxt2 = trieTree[node].children[other];
if (nxt2 == -1) return y;
node = nxt2;
}
}
return y;
}
};
struct TrieNode {
vector<int>children;
int strings_ending_here;
int strings_going_below;
int string_end_idx;
//
TrieNode() {
children.resize(26, -1);
strings_ending_here = 0;
strings_going_below = 0;
string_end_idx = -1;
}
};
struct Trie {
vector<TrieNode>TrieTree;
int sizeOfTrie = 0;
Trie() {
TrieTree.push_back(TrieNode());
sizeOfTrie++;
}
void add(string word) {
int currNode = 0;
for (auto ch : word) {
int index = ch - 'a';
if (TrieTree[currNode].children[index] == -1) {
TrieTree[currNode].children[index] = sizeOfTrie;
TrieTree.push_back(TrieNode());
sizeOfTrie++;
}
currNode = TrieTree[currNode].children[index];
TrieTree[currNode].strings_going_below++;
}
TrieTree[currNode].strings_ending_here++;
}
void add2(string& word, int idx) {
int currNode = 0;
for (auto ch : word) {
int index = ch - 'a';
if (TrieTree[currNode].children[index] == -1) {
TrieTree[currNode].children[index] = sizeOfTrie;
TrieTree.push_back(TrieNode());
sizeOfTrie++;
}
currNode = TrieTree[currNode].children[index];
TrieTree[currNode].strings_going_below++;
}
TrieTree[currNode].strings_ending_here++;
TrieTree[currNode].string_end_idx = idx;
}
bool search(string word) {
int currNode = 0;
for (auto ch : word) {
int index = ch - 'a';
if (TrieTree[currNode].children[index] == -1) return false;
currNode = TrieTree[currNode].children[index];
}
return TrieTree[currNode].strings_ending_here > 0;
}
void del(string word) {
if (search(word)== false) return;
int currNode = 0;
for (auto ch : word) {
int index = ch - 'a';
int child = TrieTree[currNode].children[index];
TrieTree[child].strings_going_below--;
if (TrieTree[child].strings_going_below == 0) {
TrieTree[currNode].children[index] = -1;
}
currNode = child;
}
TrieTree[currNode].strings_ending_here--;
}
};
};
// vector<ll>fact(maxN + 1, 0);
// vector<ll>inverseFact(maxN + 1, 0);
// void calc() {
// fact[0] = 1;
// for (int i = 1; i <= maxN; ++i) {
// fact[i] = 1LL * fact[i - 1] * i % MOD;
// }
// inverseFact[maxN] = binary_exp(fact[maxN], MOD - 2, MOD);
// for (int i = maxN - 1; i >= 0; --i) {
// inverseFact[i] = (inverseFact[i + 1] * (i + 1)) % MOD;
// }
// }
// ll C(ll n, ll r) {
// if (r < 0 || r > n) return 0;
// return 1LL * fact[n] * inverseFact[r] % MOD * inverseFact[n - r] % MOD;
// }
ll mult(ll a, ll b, ll MOD) {
ll c = ((a % MOD) * (b % MOD)) % MOD;
if (c >= MOD) {
c%=MOD;
}
return c;
}
ll add(ll a, ll b, ll MOD) {
ll c = a + b;
if (c >= MOD) c%= MOD;
return c;
}
ll divide(ll a, ll b) {
return (a % MOD) * binary_exp(b, MOD - 2 , MOD);
}
ll calc(ll a, ll b, ll c) {
// std::cout << "Tried " << a << ' ' << b << ' ' << c << '\n';
return ((a - b) * (a - b)) + ((b - c) * (b - c)) + ((c - a) * (c - a));
}
long long binpow(long long a, long long b, long long m) {
a %= m;
long long res = 1;
while (b > 0) {
if (b & 1)
res = res * a % m;
a = a * a % m;
b >>= 1;
}
return res;
}
void factorANumber(ll N) {
cin >> N;
ll res = 0;
for (long long i = 2; i * i <= N; ++i)
{
if (N % i == 0) {
int cnt = 0, moves = 0;
while (N % i == 0) {
++cnt;
N/=i;
}
while (moves * (moves + 1)/2 <= cnt) {
++moves;
}
res += (moves - 1);
}
}
cout << res + (N > 1) << '\n';
}
vector<ll> sieves(int n) {
vector<bool> prime(n + 1, true);
for (int p = 2; p * p <= n; p++) {
if (prime[p] == true) {
// Update all multiples of p greater than or
// equal to the square of it numbers which are
// multiple of p and are less than p^2 are
// already been marked.
for (int i = p * p; i <= n; i += p)
prime[i] = false;
}
}
vector<ll>res;
// Print all prime numbers
for (int p = 2; p <= n; p++)
if (prime[p])
res.push_back(p);
return res;
}
void calcSPF() {
// Allows for logn query for each number, for each number to ge ttheir primes;
// N Logn due to harmonic series.
int maxN = 1e5 + 1;
vector<bool> isPrime(maxN, true);
vector<ll> spf(1e6 + 1, 1e9);
for (ll i = 2; i < maxN; ++i) {
if (isPrime[i]) {
spf[i] = i;
for (ll j = i * i; j < maxN; j += i) {
isPrime[j] = false;
spf[j] = min(spf[j], i);
}
}
}
}
ll bitwiseAndRange(ll x, ll y) {
ll res = 0;
for (int i = 62; i >= 0; --i) {
if (((1LL << i) & x) != ((1LL << i) & y)) {
break;
} else {
res |= (x & (1LL << i));
}
}
return res;
}
map<int,int> factor(ll N) {
vector<ll>res;
map<int, int>mp;
for (long long i = 2; i * i <= N; ++i)
{
if (N % i == 0) {
int cnt = 0, moves = 0;
while (N % i == 0) {
++cnt;
res.push_back(i);
mp[i]++;
N/=i;
}
while (moves * (moves + 1)/2 <= cnt) {
++moves;
}
}
}
if (N > 1) {
res.push_back(N);
mp[N]++;
}
return mp;
}
void factor2(vector<vector<ll>>& factors, int limit) {
for (int i = 1; i <= limit; ++i) {
for (int j = i; j <= limit; j += i) {
factors[j].push_back(i);
}
}
}
constexpr ll INF = 1e17;
constexpr int INT_INF = 1e8;
using int64 = long long;
// If n ≤ 12, the time complexity can be O(n!).
// If n ≤ 25, the time complexity can be O(2^n).
// If n ≤ 100, the time complexity can be O(n4).
// If n ≤ 500, the time complexity can be O(n3).
// if n <= 5000, the time complexity can be O(n^2logn).
// If n ≤ 1e4, the time complexity can be O(n2).
// If n ≤ 1e6, the time complexity can be O(n log n).
// If n ≤ 1e8, the time complexity can be O(n).
// If n > 1e8, the time complexity can be O(log n) or O(1).
using ll = long long;
const int direc[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
const vector<long long> primes = { 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61 };
struct DSU {
vector<int> parent, sz, flag;
DSU(int n) : parent(n), sz(n, 1), flag(n, 0) {
iota(parent.begin(), parent.end(), 0);
}
int find(int x) {
if (parent[x] == x) return x;
return parent[x] = find(parent[x]);
}
bool unite(int a, int b) {
a = find(a);
b = find(b);
if (a == b) return false;
if (sz[a] < sz[b]) swap(a, b);
parent[b] = a;
sz[a] += sz[b];
return true;
}
bool unite2(int a, int b, int& c) {
a = find(a);
b = find(b);
if (a == b) return false;
if (sz[a] < sz[b]) swap(a, b);
parent[b] = a;
c = a;
sz[a] += sz[b];
return true;
}
ll size(int x) {
ll temp = sz[find(x)];
return sz[find(x)];
}
};
struct Comb {
ll C[61][61];
Comb() {
memset(C, 0, sizeof(C));
for (int n = 0; n <= 60; n++) {
C[n][0] = C[n][n] = 1;
for (int r = 1; r < n; r++) {
C[n][r] = C[n-1][r-1] + C[n-1][r];
}
}
}
ll nCr(int n, int r) const {
if (r < 0 || r > n) return 0;
return C[n][r];
}
};
ll poww(int x) {
ll ans = 1;
for (int i = 0; i < x; ++i) {
ans *= 10;
}
return ans;
}
int digits(ll x) {
int ans = 0;
while (x) {
++ans;
x/=10;
}
return ans;
}
void solve() {
namespace rng = std::ranges;
ll S, N;
cin >> S >> N;
map<ll, vector<pair<ll,ll>>>items; // weight -> [value, copies]
for (size_t i = 0; i < N; ++i)
{
ll V, W, K;
cin >> V >> W >> K;
items[W].push_back({V, K});
}
for (auto& [a, b] : items)
{
rng::sort(b, [](auto& x, auto& y) {
return x.first > y.first;
});
}
vector<pair<ll,ll>>filtered; // W, value;
for (auto& [a, b] : items)
{
ll can = S / a;
for (auto& [c, d] : b)
{
while (d > 0 && can > 0)
{
filtered.push_back({a, c});
--d;
--can;
}
if (can == 0)
{
break;
}
}
}
// 0/1 knapsack now;
std::vector<ll>dp(S + 1, 0);
for (auto& [weight, value] : filtered)
{
for (size_t i = S + 1; i-- >0; )
{
if (i >= weight)
{
dp[i] = max(dp[i], dp[i - weight] + value);
}
}
}
std::cout << rng::max(dp) << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
return 0;
}
