#include<bits/stdc++.h>
using namespace std;
#define TASK "task"
const int mxN = 5e5 + 7;
const int inf = 1e9 + 67;
struct item {
int w , v , k;
}a[mxN];
int n;
int S;
long long sum = 0;
long long dp[3000];
void solve(void) {
cin >> S >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i].v >> a[i].w >> a[i].k;
if(!a[i].w) sum += a[i].v * a[i].k;
}
memset(dp , -0x3f , sizeof dp);
dp[0] = 0;
for (int i = 1; i <= n; i++) {
int W = a[i].w , V = a[i].v , K = a[i].k;
for (int r = 0; r < W; r++) {
deque<pair<int,int>> dq;
for (int j = 0; r + j * W <= S; j++) {
int c = r + j * W;
long long val = dp[c] - 1LL * j * V;
while(dq.size() && dq.back().first <= val) dq.pop_back();
dq.emplace_back(val , j);
while(dq.size() && j - dq.front().second > K) dq.pop_front();
dp[c] = dq.front().first + 1LL * j * V;
}
}
}
long long ans = -inf;
for (int i = 0; i <= S; i++)
ans = max(ans , dp[i]);
cout << ans;
}
int main() {
ios_base :: sync_with_stdio(0);
cin.tie(0);
//freopen(TASK".inp","r",stdin);
//freopen(TASK".out","w",stdout);
int tc = 1;
//cin >> tc;
while(tc--) solve();
return 0;
}
