#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]));
}
for(int i = 1; i <= m; i++){
for(int j = m; j >= 1; j--){
int cur = 0, tot = 0;
for(pii z : w[i]){
if(z.second * i + cur <= j) cur += z.second * i, tot += z.first * z.second;
else tot += ((j - cur) / i) * z.first, cur += ((j - cur) / i) * i;
dp[j] = max(dp[j], dp[j - cur] + tot);
}
}
}
cout << dp[m];
}
