#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int s, n; cin >> s >> n;
vector<vector<pii>> items(s+1);
for (int i = 0; i < n; i++) {
int v, w, k; cin >> v >> w >> k;
items[w].push_back({v, k});
}
vector<int> weight(1), profit(1);
for (int w = 1; w <= s; w++) {
sort(items[w].begin(), items[w].end());
reverse(items[w].begin(), items[w].end());
int cnt = 0;
int max = s/w+1;
int index = 0;
while (cnt < max && index < items[w].size()) {
if (items[w][index].second == 0) {
index++;
continue;
}
weight.push_back(w);
profit.push_back(items[w][index].first);
cnt++;
items[w][index].second--;
}
}
n = weight.size();
vector<vector<int>> dp(s+1, vector<int>(n, 0));
for (int w = 1; w <= s; w++) {
for (int i = 1; i < n; i++) {
dp[w][i] = dp[w][i-1];
if (w-weight[i] >= 0) {
dp[w][i] = max(dp[w][i], profit[i] + dp[w-weight[i]][i-1]);
}
}
}
cout << dp[s][n-1] << endl;
return 0;
}
