#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main() {
int n, c;
cin >> c >> n;
vector<int> weight(n), value(n), amount(n);
for (int i = 0; i < n; i++) cin >> value[i] >> weight[i] >> amount[i];
vector<int> dp(c+1, -1); dp[0] = 0;
for (int i = 0; i < n; i++) {
for (int rem = 0; rem < weight[i]; rem++) {
deque<pair<int, int>> q;
if (dp[rem] != -1) q.push_back({dp[rem], rem});
for (int p = rem + weight[i]; p <= c; p += weight[i]) {
while (!q.empty() and q.front().second < p - weight[i] * amount[i]) q.pop_front();
while (!q.empty() and q.back().first + value[i] <= dp[p]) q.pop_back();
if (dp[p] != -1) q.push_back({dp[p], p});
if (!q.empty()) dp[p] = max(dp[p], q.front().first + (p - q.front().second) / weight[i] * value[i]);
}
}
}
cout << *max_element(dp.begin(), dp.end()) << "\n";
}
