#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;
#define db long double
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vl vector<ll>
#define vii vector<pii>
#define vll vector<pll>
#define endl '\n'
#define all(x) x.begin(), x.end()
#define fastio\
ios_base::sync_with_stdio(0);\
cin.tie(0);\
cout.tie(0)\
#define int long long
int dp[2005], n, m, x, y, z;
vii w[2005];
signed main(){
fastio;
cin >> m >> n;
for(int i = 1; i <= n; i++){
cin >> x >> y >> z;
w[y].push_back({x, z});
}
for(int i = 1; i <= m; i++){
sort(all(w[i]));
reverse(all(w[i]));
int s = 0;
for(pii j : w[i]) s += j.second;
while(s > m / i) s -= w[i].back().second, w[i].pop_back();
}
for(int i = 1; i <= m; i++){
for(pii j : w[i]){
for(int z = 1; z <= j.second; z++){
for(int k = m; k >= i; k--){
dp[k] = max(dp[k], dp[k - i] + j.first);
}
}
}
}
cout << dp[m];
}
