#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#define rep(i, s, e) for (ll i = s; i < e; i++)
#define upmax(a, b) a = max(a, b)
using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;
using vvpll = vector<vpll>;
void solve() {
ll n, S;
cin >> S >> n;
vll v(n), w(n), k(n);
vvll arr_w(S + 1);
vector<multiset<ll>> temp_arr_w(S + 1);
rep(i, 0, n) {
cin >> v[i] >> w[i] >> k[i];
rep(j, 0, min(k[i], (S + 1) / (w[i] + 1))) {
if (temp_arr_w[w[i]].empty() || temp_arr_w[w[i]].size() < (S + 1) / (w[i] + 1)) {
temp_arr_w[w[i]].insert(v[i]);
}
else if (*temp_arr_w[w[i]].begin() < v[i]) {
temp_arr_w[w[i]].erase(temp_arr_w[w[i]].begin());
temp_arr_w[w[i]].insert(v[i]);
}
}
}
rep(i, 0, S + 1) {
for (auto& it : temp_arr_w[i]) {
arr_w[i].push_back(it);
}
}
rep(i, 0, S + 1) {
sort(arr_w[i].rbegin(), arr_w[i].rend());
}
vvll dp(S + 1, vll(S + 1));
rep(i, 1, S + 1) {
rep(j, 0, S + 1) {
ll cur_w = 0;
ll cur_v = 0;
dp[i][j] = dp[i - 1][j];
rep(num_copies, 0, arr_w[i].size()) {
if (num_copies > ((S + 1) / (i + 1))) break;
cur_w += i;
cur_v += arr_w[i][num_copies];
if (cur_w <= j) {
upmax(dp[i][j], dp[i - 1][j - cur_w] + cur_v);
}
}
}
}
/*rep(i, 0, S + 1) {
rep(j, 0, S + 1) {
cout << dp[i][j] << ' ';
}
cout << endl;
}*/
cout << dp[S][S] << endl;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
solve();
}
