#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
static long long dp[100005];
static long long olddp[100005];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int S, N;
cin >> S >> N;
for(int i = 0; i <= S; i++)
dp[i] = 0;
while(N--) {
long long V, W, K;
cin >> V >> W >> K;
for(int i = 0; i <= S; i++)
olddp[i] = dp[i];
for(int r = 0; r < W; r++) {
deque<pair<long long,int>> dq;
for(int k = 0; r + k*W <= S; k++) {
int idx = r + k*W;
long long val = olddp[idx] - k * V;
while(!dq.empty() && dq.back().first <= val)
dq.pop_back();
dq.emplace_back(val, k);
while(!dq.empty() && dq.front().second < k - K)
dq.pop_front();
dp[idx] = dq.front().first + k * V;
}
}
}
cout << dp[S] << "\n";
return 0;
}
