#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using vi = vector<int>;
#define all(x) (x).begin(), (x).end()
int main() {
cin.tie(0);
cout.tie(0);
ios_base::sync_with_stdio(0);
int s, n;
cin >> s >> n;
vector<ll> v(n), w(n), k(n);
for (ll i = 0; i < n; ++i) {
cin >> v[i] >> w[i] >> k[i];
}
vector<vector<ll>> dp(2, vector<ll>(s + 1));
for (int i = 0; i < n; ++i) {
for (ll r= 0; r < w[i]; ++r) {
stack<pair<pair<ll, int>, ll>> st1, st2;
for (ll a = 0; a * w[i] + r <= s; ++a) {
if (st2.empty()) {
while (!st1.empty()) {
auto element = st1.top().first;
st1.pop();
ll maximum = st2.empty() ? element.first : max(element.first, st2.top().second);
st2.push({element, maximum});
}
}
while (!st2.empty() && a - st2.top().first.second > k[i]) {
st2.pop();
}
ll cur_val = dp[(i + 1) & 1][a * w[i] + r] - v[i] * a;
ll maximum = st1.empty() ? cur_val : max(cur_val, st1.top().second);
st1.push({{cur_val, a}, maximum});
if (!st2.empty()) maximum = max(maximum, st2.top().second);
dp[i & 1][a * w[i] + r] = maximum + a * v[i];
}
}
}
cout << dp[(n + 1) & 1][s] << '\n';
return 0;
}
