#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
ll MOD = 1e9 + 7;
struct item {
int value;
int copies;
};
void solve() {
int s, n;
cin >> s >> n;
map<int, vector<item>> item_by_weight;
for(int i = 0; i < n; i++) {
int v, w, c;
cin >> v >> w >> c;
item_by_weight[w].push_back({v, c});
}
vector<int> dp(s + 1, 0);
for(int i = 1; i <= s; i++) {
if(item_by_weight.count(i) == 0) continue;
auto vec = item_by_weight[i];
sort(vec.begin(), vec.end(), [](item a, item b) {
return a.value < b.value;
});
int times = s / i;
for(int j = 1; j <= times and vec.size() > 0; j++) {
for(int k = s; k >= i; k--) {
dp[k] = max(dp[k], dp[k - i] + vec.back().value);
}
vec.back().copies--;
if(vec.back().copies == 0) vec.pop_back();
}
}
cout << dp[s];
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
solve();
}
