// Created by Sang lớp 9
// Какого черта ты переводишь?
#include <bits/stdc++.h>
using namespace std;
#define Sang 1
#define int long long
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define endl '\n'
#define FOR(i, a, b) for(__typeof(b) i = a, _b = b; i <= _b; ++i)
#define FORD(i, a, b) for(__typeof(a) i = a, _b = b; i >= _b; --i)
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define MASK(i) (1ll<<(i))
#define BIT(t, i) (((t)>>(i))&1)
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef pair<int, ii> pii;
const int MOD = 1e9+7;
const int N = 1e5+5;
const int INF = 0x3f3f3f3f;
template <class T> bool minimize(T &a, T b) { if (a > b) { a = b; return true; } return false;}
template <class T> bool maximize(T &a, T b) { if (a < b) { a = b; return true; } return false;}
// **** ****
// * * *
// * K.B *
// * *
// * *
int S, n, dp[2005];
priority_queue<ii> Q[2005];
vector<ii> items;
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
#ifndef Sang
freopen("main.inp", "r", stdin);
freopen("main.out", "w", stdout);
#endif
cin >> S >> n;
FOR (i, 1, n){
int v, w, k; cin >> v >> w >> k;
Q[w].push({v, k});
}
FOR (i, 1, S){
int cnt = 0;
while (!Q[i].empty()){
auto T = Q[i].top(); Q[i].pop();
while (T.se && cnt < S/i){
cnt++;
T.se--;
items.pb({i, T.fi});
}
}
}
for (auto &x : items){
FORD(i, S, x.fi){
maximize(dp[i], dp[i-x.fi] + x.se);
}
}
cout << dp[S];
return 0;
}
