#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) {
deque<pair<ll, int>> q;
for (ll a = 0; a * w[i] + r <= s; ++a) {
while (!q.empty() && a - q.front().second > k[i]) {
q.pop_front();
}
ll cur_val = dp[(i + 1) & 1][a * w[i] + r] - v[i] * a;
while (!q.empty() && q.back().first <= cur_val) {
q.pop_back();
}
q.push_back({cur_val, a});
dp[i & 1][a * w[i] + r] =q.front().first + a * v[i];
}
}
}
cout << dp[(n + 1) & 1][s] << '\n';
return 0;
}
