#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) Complete knapsack nếu đủ nhiều
if (K * W >= S) {
for(int j = W; j <= S; j++){
dp[j] = max(dp[j], dp[j - W] + V);
}
continue;
}
// 2) Bounded knapsack: copy dp sang old
vector<ll> old = dp;
// Xử lý từng residue class r = 0..W-1
for(int r = 0; r < W; r++){
deque<pair<int,ll>> deq;
// t_max sao cho j = r + t*W ≤ S
int t_max = (S - r) / W;
for(int t = 0; t <= t_max; t++){
int j = r + t * W;
// Loại khỏi front các u < t-K
while(!deq.empty() && deq.front().first < t - K)
deq.pop_front();
// Tính dp[j]: không lấy món nào mới là old[j]
ll best = old[j];
if (!deq.empty()) {
// hoặc lấy thêm (t - u) món => deq.front().second + t*V
best = max(best, deq.front().second + t * V);
}
dp[j] = best;
// Tạo giá trị A_t = old[j] - t*V để phục vụ tương lai
ll At = old[j] - t * V;
// Trước khi push, pop_back các phần tử ≤ At
while(!deq.empty() && deq.back().second <= At)
deq.pop_back();
deq.emplace_back(t, At);
}
}
}
// Kết quả: dp[j] là max giá trị với trọng số = j
// nếu cần ≤ S thì lấy max dp[0..S]
ll ans = 0;
for(int j = 0; j <= S; j++)
ans = max(ans, dp[j]);
cout << ans << "\n";
return 0;
}
