#include <bits/stdc++.h>
using namespace std;
#define MAXS 2020
#define MAXN 100100
int dp[MAXS];
pair<pair<int, int>, int> items[MAXN];
int main() {
memset(dp, 0, sizeof(dp));
cin.tie(nullptr);
ios::sync_with_stdio(false);
int s, n;
cin >> s >> n;
for(int i=0;i<n;i++) {
cin >> items[i].first.first >> items[i].first.second >> items[i].second;
}
deque<pair<int, int>> dq;
for(int i=0;i<n;i++) {
int v=items[i].first.first, w=items[i].first.second, k=items[i].second;
for(int wm=0;wm<w;wm++) {
int cur=0;
for(int curw=wm; curw<=s; curw+=w) {
if(!dq.empty()&&cur-dq.back().second>k) dq.pop_back();
while(!dq.empty()&&dq.front().first+(cur-dq.front().second)*v<=dp[curw]) dq.pop_front();
dq.push_front({dp[curw], cur});
dp[curw]=dq.back().first+(cur-dq.back().second)*v;
cur++;
}
dq.clear();
}
}
cout << dp[s] << endl;
return 0;
}
