#include <bits/stdc++.h>
#include <cstdio>
#include <ios>
#define ll long long
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define sz(x) ((int)x.size())
#define endl "\n"
// loops
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define rep(a) F0R(_,a)
#define each(a,x) for (auto& a: x)
using namespace std;
template<typename T> ostream& operator<<(ostream& out, vector<T>& a){for (auto &x: a) out << x << " "; out << endl; return out;}
const int mxN = 1e5+1, mxK = 21;
const long long MOD = 998244353;
long long modpow (long long a ,long long b) {long long res = 1;a %= MOD;while (b > 0) {if (b & 1) res = (res * a) % MOD;a = (a * a) % MOD;b >>= 1;}return res;}
long long modinv ( long long q ) {return modpow (q , MOD - 2);}
void solution() {
int S, N; cin >> S >> N;
map<int, vector<array<int, 2>>> mp;
FOR(i, 0, N){
int v, w, k; cin >> v >> w >> k;
mp[w].push_back({v, k});
}
each(a, mp){
sort(rall(a.second));
}
vector<int> dp(S+1, 0);
each(a, mp){
ROF(i, 0, S+1){
int tot = 0, val=0;
bool f=0;
each(w, a.second){
FOR(k, 1, w[1]+1){
tot++; val += w[0];
if (tot*a.first <= i){
dp[i] = max(dp[i], dp[i-tot*a.first]+val);
}
else {f=1; break;}
}
if (f) break;
}
}
}
cout << dp[S] << endl;
}
int main() {
ios_base::sync_with_stdio(false); //cin.tie(nullptr);
// freopen("in.txt", "r", stdin); freopen("snakes.out", "w", stdout);
solution();
return 0;
}
