#include <bits/stdc++.h>
using namespace std;
void shawerma() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
#ifdef frenchfries
freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout);
#endif
//freopen("PROBLEMNAME.in", "r", stdin);
}
#define fi first
#define se second
#define yes cout << "YES\n";
#define no cout << "NO\n";
#define eb emplace_back
#define pb push_back
#define popb pop_back
#define popf pop_front
#define pf push_front
#define all(x) (x).begin(), (x).end()
#define allr(x) (x).rbegin(), (x).rend()
#define vi vector<int>
#define vll vector<long long>
#define vpii vector<pair<int, int>>
#define vpll vector<pair<long long, long long>>
#define vs vector<string>
#define vb vector<bool>
#define vc vector<char>
#define vvb vector<vector<bool>>
#define vvc vector<vector<char>>
#define vvi vector<vector<int>>
#define vvll vector<vector<long long>>
#define Ones(n) __builtin_popcount(n)
typedef long double ld;
typedef long long int lli;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
int dx[] = {0, 0, -1, 1, -1, 1, -1, 1};
int dy[] = {-1, 1, 0, 0, 1, 1, -1, -1};
char di[] = {'L', 'R', 'U', 'D'};
int kx[] = {-2, -1, 1, 2, 2, 1, -1, -2};
int ky[] = {1, 2, 2, 1, -1, -2, -2, -1};
const ll MOD = 1e9 + 7;
const ll N = 1e5 + 5, M = 2e5 + 5, INF = 1e18;
const ld PI = acos(-1);
void Solve() {
int balance, n;
cin >> balance >> n;
map<int, vpii> mp;
for (int i = 0; i < n; ++i) {
int val, sz;
ll k;
cin >> val >> sz >> k;
if (sz <= balance && k > 0) mp[sz].pb({val, k});
}
vvll dp(mp.size() + 1, vll(balance + 1, -INF));
dp[0][0] = 0;
int at = 1;
for (auto &[w, items]: mp) {
sort(allr(items));
for (int lim = 0; lim <= balance; ++lim) {
// option 1 : leave it
dp[at][lim] = dp[at - 1][lim];
//option 2: take it
int copies = 0, type_at = 0, used = 0;
ll profit = 0;
while ((copies + 1) * w <= lim && type_at < items.size()) {
copies++;
profit += items[type_at].fi;
// check if past was seen before to maximize either now, or then but with current's value increase?
if (dp[at - 1][lim - copies * w] != -INF) {
dp[at][lim] = max(dp[at][lim], dp[at - 1][lim - copies * w] + profit);
}
used++;
if(used == items[type_at].se){
used = 0;
type_at++;
}
}
}
at++;
}
cout << *max_element(all(dp.back())) << '\n';
}
int main() {
shawerma();
int t = 1;
//cin >> t;
while (t--) {
Solve();
}
}
