#include <bits/stdc++.h>
using namespace std;
struct Item {
long long v , w , k;
};
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int S , N;
cin >> S >> N;
vector<Item> a(N);
vector<vector<pair<long long , long long>>> now(S + 1);
for (int i = 0 ; i < N ; i++) {
cin >> a[i].v >> a[i].w >> a[i].k;
a[i].k = min(a[i].k , S * 1LL);
now[a[i].w].emplace_back(a[i].v , a[i].k);
}
vector<Item> b;
for (int i = 1 ; i <= S ; i++) {
sort(now[i].rbegin(), now[i].rend());
long long h = S;
for (int j = 0 ; j < (int)now[i].size() ; j++) {
long long can = min(h / i , now[i][j].second);
if (can == 0) break;
b.push_back({now[i][j].first , i , can});
h -= can * i;
}
}
int n = (int)b.size();
vector<pair<long long , long long>> who;
for (int i = 0 ; i < n ; i++) {
for (int j = 0 ; j < b[i].k ; j++) {
who.emplace_back(b[i].v , b[i].w);
}
}
vector<long long> dp(S + 1);
vector<bool> Reachable(S + 1);
Reachable[0] = true;
for (int i = 0 ; i < (int)who.size() ; i++) {
for (int j = S - who[i].second ; j >= 0 ; j--) {
if (j + who[i].second <= S && Reachable[j]) {
Reachable[who[i].second + j] = true;
dp[who[i].second + j] = max(dp[who[i].second + j] , dp[j] + who[i].first);
}
}
}
cout << *max_element(dp.begin(),dp.end()) << '\n';
return 0;
}
