#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define f first
#define s second
#define all(v) v.begin(), v.end()
#define dbg(v) cerr << #v << " = " << v << "\n"
#define fall(i, s, n) for(int i=s; i<n; i++)
#define rfall(i, s, n) for(int i=s; i>=n; i--)
#define get(i, t) get<i>(t)
typedef pair<int, int> pii;
typedef tuple<int, int, int> trio;
typedef tuple<int, int, int, int> squad;
void setIO(string name){
freopen((name+".in").c_str(), "r", stdin);
freopen((name+".out").c_str(), "w", stdout);
}
const int MAXN = 2e3+7;
int dp[MAXN];
int vl[MAXN][MAXN];
int32_t main(){
ios::sync_with_stdio(0); cin.tie(0);
memset(dp, -0x3f, sizeof dp), memset(vl, -0x3f, sizeof vl), dp[0]=0;
int s, n; cin >> s >> n;
vector<pii> v[MAXN];
fall(i, 0, n){
int val, w, k; cin >> val >> w >> k;
v[w].pb({val, k});
}
fall(i, 0, MAXN) sort(all(v[i]), greater<pii>{});
fall(i, 1, MAXN){
int sum=0, p=0;
fall(q, 1, MAXN){
if(p >= v[i].size()) break;
if(!v[i][p].s) p++;
if(p >= v[i].size()) break;
v[i][p].s--, sum += v[i][p].f;
vl[i][q]=sum;
}
}
fall(i, 1, s+1){
rfall(j, s, 0){
for(int q=(s-j)/i; q >= 1; q--){
dp[q*i+j] = max(dp[q*i+j], dp[j]+vl[i][q]);
}
}
}
int mx=0;
fall(i, 0, s+1) mx = max(mx, dp[i]);
cout << mx << "\n";
}
