#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int S, N;
cin >> S >> N;
vector<ll> dp(S+1, 0);
for(int i = 0; i < N; i++){
ll V, W, K;
cin >> V >> W >> K;
// 1) Nếu coi như unlimited (complete knapsack)
if (K * W >= S) {
for(int j = W; j <= S; j++){
dp[j] = max(dp[j], dp[j - W] + V);
}
continue;
}
// 2) Bounded knapsack với monotonic-queue
vector<ll> old = dp; // copy trạng thái cũ
// duyệt từng residue class mod W
for(int r = 0; r < W; r++){
deque<pair<int,ll>> deq;
// mỗi t ứng với chỉ số j = r + t*W
int tMax = (S - r) / W;
for(int t = 0; t <= tMax; t++){
int j = r + t * W;
// 2a) bỏ các u < t-K
while(!deq.empty() && deq.front().first < t - K)
deq.pop_front();
// 2b) tính dp[j]
ll best = old[j]; // không lấy item i nào
if(!deq.empty()){
// deq.front().second + t*V
best = max(best, deq.front().second + t * V);
}
dp[j] = best;
// 2c) chèn t vào deque (cho các t'>t)
// giá trị của u=t là: old[r+tW] - t*V
ll val = old[j] - (ll)t * V;
while(!deq.empty() && deq.back().second <= val)
deq.pop_back();
deq.emplace_back(t, val);
}
}
}
// Kết quả: dp[S] là max giá trị với tổng trọng số ≤ S
cout << dp[S] << "\n";
return 0;
}
