#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define st first
#define nd second
#define sz size
const int N = 1e5 + 5;
const int S = 2005;
int dp[S];
vector <pair<int, int>> val_amt[S];
bool cmp(pair<int, int> a, pair<int, int> b){
if (a.st > b.st) return 1;
return 0;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, s;
cin >> s >> n;
for (int i = 0; i < n; i ++) {
int v, w, a;
cin >> v >> w >> a;
val_amt[w].pb({v, a});
}
for (int i = 1; i <= s; i ++){
if (val_amt[i].empty()) continue;
sort(val_amt[i].begin(), val_amt[i].end(), cmp);
for (int j = s; j >= 0; j --){
int ile = 1, ind = 0, ilei = 1;
int v = 0;
while(j + ile * i <= s && ind < (int)val_amt[i].sz()){
if (ilei > val_amt[i][ind].nd){
ind ++;
ilei = 1;
continue;
}
v += val_amt[i][ind].st;
dp[j + ile * i] = max(dp[j + ile * i], dp[j] + v);
ile ++; ilei ++;
}
}
}
cout << dp[s] << "\n";
}
