#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define test(v) \
for (auto &x : (v)) { \
cout << x << " "; \
} \
cout << "\n";
#define test2d(v) \
for (int i = 0; i < (int)v.size(); i++) { \
for (int j = 0; j < (int)v[i].size(); j++) { \
cout << v[i][j] << " "; \
} \
cout << '\n'; \
}
#define pb push_back
vector<pair<int, int>> dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
mt19937 rng((int)chrono::steady_clock::now().time_since_epoch().count());
int hashp = uniform_int_distribution<int>(10, 1e9)(rng);
int hashm1 = 1e9+7;
int hashm2 = 1e9+9;
int MOD = 1e9;
int MV = 1e18;
void solve(){
int s, n;
cin >> s >> n;
vector<vector<array<int, 2>>> a(s+1);
vector<int> dp(s+1, 0);
for(int i = 0; i < n; i++){
int v, w, k;
cin >> v >> w >> k;
a[w].pb({v, k});
}
for(int i = 1; i <= s; i++){
if(a[i].empty()) continue;
sort(a[i].begin(), a[i].end(), greater<>());
vector<int> costs;
int limit = s / i;
for (auto &p : a[i]) {
if (costs.size() >= limit) break;
int val = p[0];
int count = p[1];
while (count > 0 && costs.size() < limit) {
costs.pb(val);
count--;
}
}
for (size_t x = 1; x < costs.size(); x++) {
costs[x] += costs[x-1];
}
for(int j = s; j >= i; j--){
for(int k = 1; k <= costs.size(); k++){
int prev_w = j - k * i;
if (prev_w < 0) break;
dp[j] = max(dp[j], dp[prev_w] + costs[k-1]);
}
}
}
cout << dp[s];
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
/*
freopen("snakes.in", "r", stdin);
freopen("snakes.out", "w", stdout);
*/
solve();
return 0;
}
