#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define getbit(x, i) (((x) >> (i)) & 1)
#define all(x) x.begin(), x.end()
#define TASK ""
using namespace std;
template <typename T1, typename T2> bool mini(T1 &a, T2 b) {
if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maxi(T1 &a, T2 b) {
if (a < b) {a = b; return true;} return false;
}
const long long inf = 1e18;
const int mod = 1e9 + 7;
const int N = 1e5 + 7;
int s, n;
int dp[2006];
int v[N], w[N], k[N];
vector <int> a[2006];
vector <pair <int, int>> item[2006];
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> s >> n;
for (int i = 1; i <= n; ++i) {
cin >> v[i] >> w[i] >> k[i];
item[w[i]].emplace_back(v[i], k[i]);
}
for (int i = 0; i <= s; ++i) sort(all(item[i]));
memset(dp, -0x3f, sizeof dp);
dp[0] = 0;
for (int i = 1; i <= s; ++i) {
int lim = s / i;
while (item[i].size() && lim > 0) {
auto &[value, cnt] = item[i].back();
if (cnt > 0) {
cnt--; lim--;
a[i].emplace_back(value);
} else item[i].pop_back();
}
}
for (int i = 1; i <= s; ++i)
for (int j : a[i]) for (int k = s; k >= i; --k) maxi(dp[k], dp[k - i] + j);
cout << dp[s];
}
