#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1e6 + 15;
#define ll long long
ll numItems, capacity;
ll value[MAX_N];
ll weight[MAX_N];
ll itemCount[MAX_N];
vector<pair<ll, int>> itemsByWeight[4000];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> capacity >> numItems;
for (int i = 0; i < numItems; i++)
cin >> value[i] >> weight[i] >> itemCount[i];
ll maxItemCount = *max_element(itemCount, itemCount + numItems);
if (numItems == 1) {
cout << value[0] * min(capacity / weight[0], itemCount[0]) << '\n';
} else if (1 <= numItems && numItems <= 100 && maxItemCount <= 10) {
ll dp[4000];
memset(dp, 0, sizeof dp);
for (int i = 0; i < numItems; i++) {
for (int w = capacity; w >= 0; w--) {
for (ll j = 1; j <= itemCount[i]; j++) {
if (w + j * weight[i] > capacity)
break;
if ((dp[w] > 0 || w == 0)) {
dp[w + j * weight[i]] = max(dp[w + j * weight[i]], dp[w] + j * value[i]);
}
}
}
}
ll ans = 0;
for (int i = 1; i <= capacity; i++)
ans = max(ans, dp[i]);
cout << ans << '\n';
} else {
ll dp[4000];
ll ans = 0;
memset(dp, 0, sizeof dp);
for (int i = 0; i < numItems; i++)
itemsByWeight[weight[i]].push_back({value[i], itemCount[i]});
for (int i = 1; i <= capacity; i++) {
if (itemsByWeight[i].size() == 0)
continue;
sort(itemsByWeight[i].begin(), itemsByWeight[i].end(), greater<pair<int, int>>());
int id = 0;
for (int j = 1; j * i <= capacity; j++) {
if (id >= itemsByWeight[i].size())
break;
for (int w = capacity; w >= 0; w--) {
if ((w == 0 || dp[w] > 0) && w + i <= capacity) {
dp[w + i] = max(dp[w + i], dp[w] + itemsByWeight[i][id].first);
}
}
--itemsByWeight[i][id].second;
if (itemsByWeight[i][id].second == 0)
id++;
}
}
for (int i = 1; i <= capacity; i++)
ans = max(ans, dp[i]);
cout << ans << '\n';
}
return 0;
}
