#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll s, n, a, b, c;
ll dpupd[2005], dpold[2005];
priority_queue<pair<ll, int>> pq;
int main() {
cin.tie(0) -> sync_with_stdio(0);
cin >> s >> n;
for(int i=1;i<=n;i++) {
cin >> a >> b >> c;
for(int i=0;i<b;i++) {
for(int j=i,k=0;j<=s;j+=b,k++) {
if(!pq.empty()) {
while(k - pq.top().second > c) pq.pop();
dpupd[j] = pq.top().first + k*a;
} else dpupd[j] = 0;
pq.emplace(dpold[j] - k*a, k);
}
while(!pq.empty()) pq.pop();
}
//cout << s << '\n';
for(int i=0;i<=s;i++) dpold[i] = dpupd[i];
//for(int i=0;i<=s;i++) cout << (dpold[i] = dpupd[i]) << ' '; cout << '\n';
}
cout << dpold[s];
}
