#pragma GCC optimize("O3,inline")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int ll
using ii = pair<int, int>;
using iii = pair<ii, int>;
constexpr int MAXN = 100000 + 5;
constexpr int INF = 1e18 + 5;
constexpr int LOG = 20;
template <class T>
std::vector<T> sliding_max(const std::vector<T>& a,int w) {
int n=(int)a.size(); std::deque<int> dq; std::vector<T> out;
for (int i=0;i<n;i++) {
while (!dq.empty() && dq.front()<=i-w) dq.pop_front();
while (!dq.empty() && a[dq.back()]<a[i]) dq.pop_back();
dq.push_back(i);
out.push_back(a[dq.front()]);
}
return out;
}
// iii is pair<ii, int>
// pair<pair<value, weight>, num of this type>
int ans(const vector<iii> &items, int S) {
int N = items.size();
vector<int> dp_prev(S+1);
vector<int> dp_curr(S+1);
for (int i = 0; i < N; ++i) {
swap(dp_curr, dp_prev);
for (int m = 0; m < items[i].first.second; ++m) {
vector<int> pr;
for (int f = m; f <= S; f += items[i].first.second) {
pr.emplace_back(dp_prev[f]);
}
int thingies = pr.size();
for (int j = 0; j < thingies; ++j) {
pr[j] -= j * items[i].first.first;
}
vector<int> res = sliding_max(pr, items[i].second + 1);
for (int j = 0; j < thingies; ++j) {
dp_curr[m + j * items[i].first.second] = res[j] + j * items[i].first.first;
}
}
}
return *max_element(dp_curr.begin(), dp_curr.end());
}
signed main() {
ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
int S, N; cin >> S >> N;
vector<iii> items(N);
for (int i = 0; i < N; ++i) {
cin >> items[i].first.first >> items[i].first.second >> items[i].second;
}
cout << ans(items, S);
}
