// author : _anhtun.hi_
#include <bits/stdc++.h>
#define ll long long
#define ii pair<ll, ll>
#define fi first
#define se second
#define c_bit(i) __builtin_popcountll(i)
#define Bit(mask, i) ((mask >> i) & 1)
#define onbit(mask, i) ((mask) bitor (1LL << i))
#define offbit(mask, i) ((mask) &~ (1LL << i))
#define all(data) data.begin(), data.end()
#define reset(h, v) memset(h, v, sizeof h)
#define Forv(i, a) for(auto& i : a)
#define For(i, a, b) for(int i = a; i <= b; ++i)
#define Ford(i, a, b) for(int i = a; i >= b; --i)
using namespace std;
void maximize(auto &a, auto b) {a = max(a, b);}
void minimize(auto &a, auto b) {a = min(a, b);}
#define int long long
const int dx[] = {0, 0, +1, -1}, dy[] = {-1, +1, 0, 0};
const int MAXN = 2e3 + 100, LOG = 20, base = 311;
const ll mod = 1e9 + 7;
const ll oo = 1e18;
int n, s;
vector<ii> List[MAXN];
ll a[MAXN][MAXN], dp[MAXN][MAXN];
void Solve(){
cin >> s >> n;
For(i, 1, n){
int v, w, k;
cin >> v >> w >> k;
List[w].push_back({v, k});
}
reset(dp, 0); dp[0][0] = 0;
For(w, 1, s){
sort(all(List[w]), [&](ii a, ii b){
return (a.fi > b.fi) || (a.fi == b.fi && a.se > b.se);
});
// For(S, 0, s) maximize(dp[w][S], dp[w - 1][S]);
// if (List[w].size()) {
int id = 0;
for(auto [v, k] : List[w]){
For(j, 1, k) {
a[w][++id] = v;
if (id > s / w) break;
}
if (id > s / w) break;
}
For(S, 0, s) {
ll sum = 0;
For(j, 0, id) if(S - w * j >= 0) {
sum += a[w][j];
maximize(dp[w][S], dp[w - 1][S - w * j] + sum);
}
}
// }
}
cout << dp[s][s] << '\n';
}
signed main(){
ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
if (fopen("NOI18_knapsack.inp", "r")){
freopen("NOI18_knapsack.inp", "r", stdin);
freopen("NOI18_knapsack.out", "w", stdout);
}
int tc = 1; // cin >> tc;
while (tc --) Solve();
return 0;
}
