#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
static long long dp[100005];
static long long olddp[100005];
struct Item {
long long V, W, K;
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int S, N;
cin >> S >> N;
vector<Item> items(N);
for(int i = 0; i < N; i++)
cin >> items[i].V >> items[i].W >> items[i].K;
// sort theo W
sort(items.begin(), items.end(), [](const Item &a, const Item &b){
return a.W < b.W;
});
// init dp
for(int i = 0; i <= S; i++)
dp[i] = 0;
// duyệt theo từng group cùng W
for(int i = 0; i < N; ) {
int j = i;
long long W = items[i].W;
// xác định đoạn cùng W
while(j < N && items[j].W == W) j++;
// group là [i, j)
// sort trong group theo V giảm dần
sort(items.begin() + i, items.begin() + j, [](const Item &a, const Item &b){
return a.V > b.V;
});
// xử lý từng item trong group
for(int t = i; t < j; t++) {
long long V = items[t].V;
long long K = items[t].K;
// copy dp
for(int x = 0; x <= S; x++)
olddp[x] = dp[x];
// monotonic queue bounded knapsack
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;
}
}
}
i = j;
}
cout << dp[S] << "\n";
return 0;
}
