#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int S, N;
cin >> S >> N; // ⚠️ Thứ tự đúng theo đề bài: S trước, N sau
vector<long long> dp(S + 1, 0LL);
for (int i = 0; i < N; ++i) {
long long V, W, K;
cin >> V >> W >> K;
if (W == 0 || K == 0) continue;
if (W > S) continue; // Không thể lấy được vì nặng hơn sức chứa
long long max_take = min(K, (long long)(S / W));
// Nếu đủ để lấp đầy -> unbounded
if (max_take * W >= S) {
for (int s = W; s <= S; ++s) {
dp[s] = max(dp[s], dp[s - W] + V);
}
} else {
// bounded -> binary splitting
long long remain = max_take;
for (long long t = 1; remain > 0; t <<= 1) {
long long num = min(t, remain);
int weight = (int)(num * W);
long long value = num * V;
for (int s = S; s >= weight; --s) {
dp[s] = max(dp[s], dp[s - weight] + value);
}
remain -= num;
}
}
}
cout << *max_element(dp.begin(), dp.end()) << "\n";
return 0;
}
