#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll dp[2005];
vector<pair<int, int>> vec[2005];
int s, n;
int val, wei, amo;
int touse[2005];
void upd(ll val, ll x) {
for(int i=s-x;i>=0;i--) {
dp[i+x] = max(dp[i+x], dp[i] + val);
}
}
int main() {
cin.tie(0) -> sync_with_stdio(0);
cin >> s >> n;
for(int i=0;i<n;i++) {
cin >> val >> wei >> amo;
vec[wei].emplace_back(val, amo);
}
for(int i=0;i<=s;i++) sort(vec[i].begin(), vec[i].end());
for(int i=1;i<=s;i++) touse[i] = (s+i-1)/i;
for(int i=1;i<=s;i++) {
//cout << touse[i] << ' ';
while((touse[i]--) && !vec[i].empty()) {
upd(vec[i].back().first, i);
if(!(--vec[i].back().second)) vec[i].pop_back();
}
//for(int i=0;i<=s;i++) cout << dp[i] << ' ';
//cout << '\n';
}
cout << dp[s];
}
