//test by gpt 4
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int S, N;
cin >> S >> N;
struct Item { ll v, w, k; };
vector<Item> items(N);
for (int i = 0; i < N; i++) {
cin >> items[i].v >> items[i].w >> items[i].k;
}
// dp[x] = max total value with weight exactly x
const ll NEG_INF = LLONG_MIN / 4;
vector<ll> dp(S+1, NEG_INF);
dp[0] = 0;
for (auto &it : items) {
ll V = it.v, W = it.w, K = it.k;
ll rem = K;
// binary‐split the K copies into sums of powers of two
for (ll batch = 1; rem > 0; batch <<= 1) {
ll take = min(batch, rem);
rem -= take;
ll weight = take * W;
ll value = take * V;
if (weight > S)
continue;
// 0–1 knapsack for this “batch” chunk
for (int x = S; x >= weight; x--) {
if (dp[x - weight] != NEG_INF) {
dp[x] = max(dp[x], dp[x - weight] + value);
}
}
}
}
// answer = best over all weights ≤ S
ll ans = 0;
for (int x = 0; x <= S; x++) {
ans = max(ans, dp[x]);
}
cout << ans << "\n";
return 0;
}
