#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
// freopen("template.in", "r", stdin);
// freopen("template.out", "w", stdout);
int s, n; cin >> s >> n;
vector<int> v(n + 1), w(n + 1), k(n + 1);
for (int i = 1; i <= n; ++i){
cin >> v[i] >> w[i] >> k[i];
k[i] = min(k[i], s);
}
vector<int> f(s + 1, 0);
for (int i = 1; i <= n; ++i){
for (int j = 0; j < w[i]; ++j){
deque<pair<int, int>> mq;
for (int c = j; c <= s; c += w[i]){
int l = (c - j)/w[i];
int cval = f[c] - l * v[i];
if (!mq.empty() && mq.front().second == l - k[i] - 1){mq.pop_front();}
while (!mq.empty() && mq.back().first < cval){mq.pop_back();}
mq.push_back({cval, l});
f[c] = mq.front().first + l * v[i];
}
}
}
cout << f[s];
}
