#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MN = 1e5 + 5;
ll V[MN], W[MN], K[MN];
ll dp[2][2020], used[2020];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int S, n;
cin >> S >> n;
for (int i = 1; i <= n; i++) cin >> V[i] >> W[i] >> K[i];
vector<int> ord(n);
iota(ord.begin(), ord.end(), 1);
sort(ord.begin(), ord.end(), [&](int a, int b) { return V[a] > V[b]; });
int t = 0;
for (int i : ord) {
if (used[W[i]] * W[i] > S) continue;
int w = W[i];
vector<deque<ll>> dq(w); // one deque per remainder
for (int j = 0; j <= S; j++) {
int R = j % w, D = j / w;
// push new element into deque
ll val = dp[t ^ 1][j] - D * V[i];
while (!dq[R].empty() && dq[R].back() < val)
dq[R].pop_back();
dq[R].push_back(val);
// pop out-of-window element
if (j >= w * (K[i] + 1)) {
ll old_val = dp[t ^ 1][j - w * (K[i] + 1)] - (D - K[i] - 1) * V[i];
if (!dq[R].empty() && dq[R].front() == old_val)
dq[R].pop_front();
}
dp[t][j] = dq[R].empty() ? 0 : dq[R].front() + D * V[i];
}
t ^= 1;
used[W[i]] += K[i];
}
cout << dp[t ^ 1][S] << "\n";
}
