#include <bits/stdc++.h>
using namespace std;
void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail>
void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#define rng_init mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define all(x) (x).begin(), (x).end()
#define sz(x) int(x.size())
using ll = long long;
const int MAXN = 1e5 + 5;
const ll INF = 1e18;
void subtask4() {
int N, S;
cin >> S >> N;
vector<pair<ll, ll>> items;
for (int i = 0; i < N; i++) {
ll V, W, K;
cin >> V >> W >> K;
if (W > S) continue;
ll inc = 1;
while (inc <= K) {
items.emplace_back(V * inc, W * inc);
inc *= 2;
}
items.pop_back();
inc /= 2;
inc--;
if (K == inc) continue;
items.emplace_back(V * (K - inc), W * (K - inc));
}
vector<ll> dp(S + 1, -INF);
dp[0] = 0;
for (const auto &[val, wt] : items) {
if (S - wt < 0) continue;
for (int i = S - wt; i >= 0; i--) {
dp[i + wt] = max(dp[i + wt], dp[i] + val);
}
}
cout << *max_element(all(dp));
}
void solve() {
int N, S;
cin >> S >> N;
vector<pair<ll, ll>> A[S + 1];
for (int i = 0; i < N; i++) {
ll V, W, K;
cin >> V >> W >> K;
A[W].emplace_back(V, K);
}
vector<pair<ll, ll>> items;
for (int i = 1; i <= S; i++) {
sort(all(A[i]), greater<>());
int take = S / i + 1, j = 0;
while (take && j < sz(A[i])) {
if (A[i][j].second == 0) {
j++;
continue;
}
A[i][j].second--;
take--;
items.emplace_back(A[i][j].first, i);
}
}
vector<ll> dp(S + 1, -INF);
dp[0] = 0;
for (const auto &[val, wt] : items) {
if (S - wt < 0) continue;
for (int i = S - wt; i >= 0; i--) {
dp[i + wt] = max(dp[i + wt], dp[i] + val);
}
}
cout << *max_element(all(dp));
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
// subtask4();
solve();
}
