#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int S, N;
cin >> S >> N;
vector<pair<int, long long>> items; // {weight, value}
for (int i = 0; i < N; i++) {
long long V;
int W, K;
cin >> V >> W >> K;
// Skip if single item is too heavy
if (W > S) continue;
// Binary representation optimization
int cnt = 1;
while (cnt <= K) {
if ((long long)W * cnt > S) break; // Stop if weight exceeds capacity
items.push_back({W * cnt, V * cnt});
K -= cnt;
cnt *= 2;
}
// Add remainder if it fits
if (K > 0 && (long long)W * K <= S) {
items.push_back({W * K, V * K});
}
}
// Standard 0/1 knapsack with space optimization
vector<long long> dp(S + 1, 0);
for (auto& [weight, value] : items) {
for (int w = S; w >= weight; w--) {
dp[w] = max(dp[w], dp[w - weight] + value);
}
}
cout << dp[S] << '\n';
return 0;
}
