#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;
unordered_map<long long, vector<pair<long long,long long>>> groups;
groups.reserve(N);
for(int i = 0; i < N; i++) {
long long V, W, K;
cin >> V >> W >> K;
groups[W].push_back({V, K});
}
for(int i = 0; i <= S; i++)
dp[i] = 0;
for(auto &g : groups) {
long long W = g.first;
auto &items = g.second;
sort(items.begin(), items.end(), greater<>());
for(auto &it : items) {
long long V = it.first;
long long K = it.second;
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;
}
