#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pl;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tpl;
#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())
const int mn = 1e5 + 5;
ll V[mn], W[mn], K[mn], dp[2][2020], used[2020];
struct dqTrick {
deque<ll> dq;
void push (ll x) {
while (dq.size() && dq.back() < x) dq.pop_back();
dq.push_back(x);
}
void pop (ll x) {
if (dq.size() && dq.front() == x) dq.pop_front();
}
ll best() { return (dq.empty() ? LLONG_MIN : dq.front()); }
};
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int S, n; cin >> S >> n;
for (int i = 1; i <= n; i++) cin >> V[i] >> W[i] >> K[i];
vector<int> ord(n);
for (int i = 1; i <= n; i++) ord[i - 1] = i;
sort(all(ord), [&] (int a, int b) { return V[a] > V[b]; });
for (int it = 0, t = 0; it < n; it++) {
int i = ord[it];
used[W[i]] += K[i];
if (used[W[i]] * W[i] > S) continue;
vector<dqTrick> opt(W[i]);
for (int j = 0; j <= S; j++) {
int R = j % W[i], D = j / W[i];
opt[R].push(dp[t ^ 1][j] - D * V[i]);
if (j >= W[i] * (K[i] + 1))
opt[R].pop(dp[t ^ 1][j - W[i] * (K[i] + 1)] - (D - K[i] - 1) * V[i]);
dp[t][j] = opt[R].best() + D * V[i];
}
t ^= 1;
}
cout << dp[(n - 1) & 1][S];
return 0;
}
