#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
int main() {
// Optimize I/O
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int S, N;
if (!(cin >> S >> N)) return 0;
// dp[w] stores the maximum value for weight w
// Use long long because value can be up to 10^6 and we have 100 items (10^8 total)
vector<ll> dp(S + 1, 0);
for (int i = 0; i < N; i++) {
ll V, W, K;
cin >> V >> W >> K;
// Case 1: Effectively Unbounded Knapsack
// If total weight of these items exceeds basket capacity,
// the limit K doesn't actually matter.
if (K * W >= S) {
for (int j = W; j <= S; j++) {
dp[j] = max(dp[j], dp[j - W] + V);
}
}
// Case 2: Bounded Knapsack using Binary Grouping
else {
ll current_k = K;
for (int b = 1; current_k >= b; b <<= 1) {
ll bundle_w = W * b;
ll bundle_v = V * b;
// Standard 0/1 Knapsack (Backward loop)
for (int j = S; j >= bundle_w; j--) {
dp[j] = max(dp[j], dp[j - bundle_w] + bundle_v);
}
current_k -= b;
}
// Add the remaining items as a final bundle
if (current_k > 0) {
ll bundle_w = W * current_k;
ll bundle_v = V * current_k;
for (int j = S; j >= bundle_w; j--) {
dp[j] = max(dp[j], dp[j - bundle_w] + bundle_v);
}
}
}
}
// The answer is the maximum value we found within capacity S
ll max_val = 0;
for (int i = 0; i <= S; i++) {
max_val = max(max_val, dp[i]);
}
cout << max_val << endl;
return 0;
}
