#include <bits/stdc++.h>
#define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
using namespace std;
const int N = 1e5 + 5, M = 2005;
int S, n;
long long dp[N];
vector<pair<long long, long long>> ve[M], sus;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
// file("A") else file("task");
cin >> S >> n;
for(int i = 1; i <= n; ++i) {
int v, w, k;
cin >> v >> w >> k;
ve[w].emplace_back(v, k);
}
for(int i = 1; i <= S; ++i) {
sort(ve[i].begin(), ve[i].end(), greater<pair<long long, long long>>());
int rem = S / i;
for(int j = 0; j < (int)ve[i].size() && rem > 0; ++j) {
int sel = min((long long)rem, ve[i][j].second);
rem -= sel;
while(sel--) sus.emplace_back(ve[i][j].first, i);
}
}
for(pair<long long, long long> p : sus) {
for(int i = S; i >= p.second; --i) {
dp[i] = max(dp[i], dp[i - p.second] + p.first);
}
}
cout << dp[S] << '\n';
return 0;
}
