#include <bits/stdc++.h>
#pragma GCC optimize("O3", "unroll-loops")
using namespace std;
using ll = long long;
const int N = 100'000 + 10;
const int WEIGHT = 2'000 + 10;
int n, maxWeight;
int values[N], weight[N], cnt[N];
namespace sub3 {
bool check() {
return (n <= 100 && *max_element(cnt + 1, cnt + 1 + n) <= 10);
}
void solve() {
vector<vector<ll>> dp(n + 10, vector<ll>(maxWeight + 10, 0));
for (int i = 0; i < n; ++ i) {
for (int s = 0; s <= maxWeight; ++ s) {
int cost = values[i + 1], w = weight[i + 1];
ll curCost = 0, curW = 0;
for (int j = 0; j <= cnt[i + 1]; ++ j) {
if (curW + s > maxWeight) break;
dp[i + 1][s + curW] = max(dp[i + 1][s + curW], dp[i][s] + curCost);
curCost += cost;
curW += w;
}
}
}
cout << *max_element(dp[n].begin(), dp[n].end());
}
}
namespace sub4 {
bool check() {
return (n <= 100);
}
vector<pair<ll, ll>> bag;
void splitItem(int cost, int w, int cnt) {
for (ll pw = 1; cnt >= pw; pw *= 2ll) {
bag.push_back(make_pair(1ll * cost * pw, 1ll * w * pw));
cnt -= pw;
}
if (cnt > 0) {
bag.push_back(make_pair(1ll * cost * cnt, 1ll * w * cnt));
}
}
void solve() {
bag.push_back(make_pair(0, 0));
for (int i = 1; i <= n; ++ i) splitItem(values[i], weight[i], cnt[i]);
n = (int) bag.size() - 1;
vector<vector<ll>> dp(n + 10, vector<ll>(maxWeight + 10, 0));
for (int i = 0; i < n; ++ i) {
ll cost = bag[i + 1].first, w = bag[i + 1].second;
for (int s = 0; s <= maxWeight; ++ s) {
dp[i + 1][s] = max(dp[i + 1][s], dp[i][s]);
if (w + s <= maxWeight) {
dp[i + 1][s + w] = max(dp[i + 1][s + w], dp[i][s] + cost);
}
}
}
cout << *max_element(dp[n].begin(), dp[n].end());
}
}
namespace sub5 {
vector<int> position;
vector<pair<int, int>> bag;
void makeGroup(int l, int r) {
int w = weight[position[l]];
int maxCnt = maxWeight / w;
for (int i = l; maxCnt > 0 && i <= r; ++ i) {
int idx = position[i];
int cost = values[idx];
while (maxCnt > 0 && cnt[idx] > 0) {
-- maxCnt;
-- cnt[idx];
bag.push_back(make_pair(cost, w));
}
}
}
void solve() {
for (int i = 1; i <= n; ++ i) position.push_back(i);
sort(position.begin(), position.end(), [&] (int lhs, int rhs) -> bool {
if (weight[lhs] != weight[rhs]) return weight[lhs] < weight[rhs];
return values[lhs] > values[rhs];
});
bag.push_back(make_pair(0, 0));
for (int l = 0, r = 0; l < n; l = r) {
while (r < n && weight[position[l]] == weight[position[r]]) ++ r;
makeGroup(l, r - 1);
}
n = (int) bag.size() - 1;
vector<vector<ll>> dp(n + 10, vector<ll>(maxWeight + 10, 0));
for (int i = 0; i < n; ++ i) {
ll cost = bag[i + 1].first, w = bag[i + 1].second;
for (int s = 0; s <= maxWeight; ++ s) {
dp[i + 1][s] = max(dp[i + 1][s], dp[i][s]);
if (w + s <= maxWeight) {
dp[i + 1][s + w] = max(dp[i + 1][s + w], dp[i][s] + cost);
}
}
}
cout << *max_element(dp[n].begin(), dp[n].end());
}
}
int32_t main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr); std::cout.tie(nullptr);
cin >> maxWeight >> n;
for (int i = 1; i <= n; ++ i) cin >> values[i] >> weight[i] >> cnt[i];
if (sub3::check()) {
sub3::solve();
return 0;
}
if (sub4::check()) {
sub4::solve();
return 0;
}
sub5::solve();
return (0 ^ 0);
}
/// Code by vuavisao
