#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);
ll s, n; cin >> s >> n;
vector<ll> v(n + 1), w(n + 1), k(n + 1);
for (ll i = 1; i <= n; ++i){
cin >> v[i] >> w[i] >> k[i];
}
vector<ll> f(s + 1);
ll cval; ll l;
deque<pair<ll, ll>> mq;
for (ll i = 1; i <= n; ++i){
for (ll j = 0; j < w[i]; ++j){
mq = deque<pair<ll, ll>>();
for (ll c = j; c <= s; c += w[i]){
l = (c - j)/w[i];
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];
}
