#include <bits/stdc++.h>
#define d1(x) cout << #x << " : " << x << endl << flush
#define d2(x, y) cout << #x << " : " << x << " " << #y << " : " << y << endl << flush
#define d3(x, y, z) cout << #x << " : " << x << " " << #y << " : " << y << " " << #z << " : " << z << endl << flush
#define d4(x, y, z, a) cout << #x << " : " << x << " " << #y << " : " << y << " " << #z << " : " << z << " "<< #a << " : " << a << endl << flush
#define ld long double
#define ll long long
#define pb push_back
#define arr(x) array <ll, x>
#define endl '\n'
#define int long long
#define lc v << 1
#define rc v << 1 | 1
using namespace std;
const int INF = 1e9 + 24 + (33 / 10); // 33 ---> 34
const int MAXN = 2e3 + 24 + (33 / 10); // 33 ---> 34
vector <arr(2)> v[MAXN];
vector <int> h[MAXN];
int dp[MAXN], dpp[MAXN];
int b[MAXN], w[MAXN], k[MAXN];
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int s, n;
cin >> s >> n;
for(int i = 1; i <= n; i++){
cin >> b[i] >> w[i] >> k[i];
v[w[i]].pb({b[i], k[i]});
}
for(int i = 1; i <= s; i++){
sort(v[i].begin(), v[i].end(), greater<arr(2)>());
int cnt = 0;
for(auto [z, ted] : v[i]){
while(ted > 0 && (cnt + 1) <= s / i){
h[i].pb(z);
ted--;
cnt++;
}
}
}
int ans = 0;
for(int i = 1; i <= s; i++){ // pref
// d1(i);
int eli = 0;
for(int j = 0; j < h[i].size(); j++){ // teded
eli += h[i][j];
for(int k = 1; k <= s; k++){ // dp
if(k - (j + 1) * i < 0)
continue;
dpp[k] = dp[k - (j + 1) * i] + eli;
// d3(j, k, dpp[k]);
}
}
for(int k = 1; k <= s; k++){
dp[k] = max(dp[k], dpp[k]);
ans = max(ans, dp[k]);
}
}
cout << ans << endl;
}
// Ey To Bahane! :_)))
