# include <bits/stdc++.h>
using namespace std;
# define ll long long
# define ld long double
# define pii pair <int, int>
# define pll pair <ll, ll>
# define nl '\n'
# define sz(x) (int)(x).size()
# define all(x) (x).begin(), (x).end()
# define deb(x) cerr << #x << " = " << x << endl;
# define file(s) if (fopen(s".in", "r")) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)
const int maxn = (int)1e5 + 3;
const ll inf = (ll)1e9 + 0;
const int mod = (int)1e9 + 7;
const bool T = 0;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int s, n;
array<int, 3> a[maxn];
vector <pii> v[2002];
int dp[2][2002];
void ma1n () {
cin >> s >> n;
for (int i = 1; i <= n; ++i) {
cin >> a[i][0] >> a[i][1] >> a[i][2];
a[i][2] = min(a[i][2], s / a[i][1]);
v[a[i][1]].push_back({a[i][0], a[i][2]});
}
bool cur = 1, prev = 0;
for (int i = 1; i <= s; ++i) {
sort(all(v[i]), greater<pii>());
for (int x = 0; x <= s; ++x) {
int c = 0, sum = 0;
for (int j = 0; j < sz(v[i]); ++j) {
int pnt = 0;
while ((c + 1) * i <= x && pnt < v[i][j].second) {
c++;
pnt++;
sum += v[i][j].first;
dp[cur][x] = max(dp[cur][x], dp[prev][x - c * i] + sum);
}
}
}
for (int j = 0; j <= s; ++j) {
dp[cur][j] = max(dp[cur][j], dp[prev][j]);
dp[prev][j] = 0;
}
swap(prev, cur);
}
cout << dp[prev][s] << nl;
}
signed main () {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int ttt = 1;
if (T) cin >> ttt;
while (ttt--) {
ma1n();
}
return 0;
}
