#include <bits/stdc++.h>
using namespace std;
#define int long long
// #define ll long long
#define MAX 20005
vector<int> dp(MAX);
int S, n;
struct menkh {
int value, weight, num;
};
void solve() {
cin >> S >> n;
vector<menkh> items(n + 1);
int maxWeight = 0;
for (int i = 1; i <= n; i++) {
cin >> items[i].value >> items[i].weight >> items[i].num;
maxWeight = max(maxWeight, items[i].weight);
}
vector<pair<int, int>> group[maxWeight + 1];
for (int i = 1; i <= n; i++) {
group[items[i].weight].push_back({items[i].value, items[i].num});
}
for (int i = 1; i <= maxWeight; i++) {
sort(group[i].begin(), group[i].end(), [](pair<int, int> &A, pair<int, int> &B) {
return A.first > B.first;
});
}
dp[0] = 0;
for (int w = 1; w <= maxWeight; w++) {
if (group[w].empty()) continue;
vector<int> old_dp = dp;
for (pair<int, int> cur : group[w]) {
int value = cur.first;
int num = min(S / w, cur.second);
for (int k = 1; k <= num; k++) {
for (int j = S; j >= k * w; j--) {
dp[j] = max(dp[j], old_dp[j - k * w] + k * value);
}
}
old_dp = dp;
}
}
cout << dp[S] << '\n';
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int t = 1;
// int t; cin >> t;
while (t--) solve();
}
// 1 MB = 1000000 bytes
// 1 int = 4 bytes
// memory consumption: (sizeof(...)_int * 4) / 1000000
