#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define FASTIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int main() {
FASTIO
int S, N;
cin >> S >> N;
vector<ll> dp(S + 1, -1e18);
dp[0] = 0;
for (int i = 0; i < N; i++) {
int v, w;
ll k;
cin >> v >> w >> k;
vector<ll> ndp = dp;
for (int r = 0; r < w; r++) {
deque<pair<ll,int>> dq;
for (int j = r; j <= S; j += w) {
ll cur = dp[j] - (ll)(j / w) * v;
while (!dq.empty() && dq.back().first <= cur)
dq.pop_back();
dq.emplace_back(cur, j / w);
while (!dq.empty() && dq.front().second < (j / w) - k)
dq.pop_front();
ndp[j] = dq.front().first + (ll)(j / w) * v;
}
}
dp.swap(ndp);
}
ll ans = 0;
for (int i = 0; i <= S; i++)
ans = max(ans, dp[i]);
cout << ans;
return 0;
}
