#include <bits/stdc++.h>
using namespace std;
#define ent "\n"
#define all(a) (a).begin(), (a).end()
#define int int64_t
#define pii pair<int,int>
using ld = long double;
const int MOD = 1e9 + 7;
const int inf = 1e18;
int32_t main() {
ios::sync_with_stdio(false);
cin.tie(0);
int s, n;
cin >> s >> n;
vector<array<int, 3>> a(n);
bool isk1 = 1;
for (int i = 0; i < n; ++i) {
cin >> a[i][0] >> a[i][1] >> a[i][2];
if (a[i][2] != 1) {
isk1 = 0;
}
}
if (n == 1) {
int ans = 0;
for (int i = 1; i <= a[0][2]; ++i) {
if (a[0][1] * i <= s) {
ans = a[0][0] * i;
}
}
cout << ans;
}
else if (isk1) {
// dp[i][j] = i elements with j -> cost
vector<vector<int>> dp(n+1,vector<int> (s+1,-inf));
dp[0][0] = 0;
for (int i = 0; i < n; ++i) {
if (a[i][1] <= s) {
dp[1][a[i][1]] = a[i][2];
}
}
for (int i = 1; i <= n; ++i) {
for (int j = 0; j <= s; ++j) {
dp[i][j] = dp[i - 1][j];
int prev = j - a[i - 1][1];
if (prev >= 0 && dp[i - 1][prev] != -inf) {
dp[i][j] = max(dp[i][j], dp[i - 1][prev] + a[i - 1][0]);
}
}
}
int ans = 0;
for (int i = 1; i <= n; ++i) {
for (int j = 0; j <= s; ++j) {
ans = max(ans, dp[i][j]);
}
}
cout << ans;
}
}
int binpow(int base, int power) {
if (power == 0) return 1;
if (power == 1) return base;
int x = binpow(base, power / 2);
if (power & 1) return x * x * base;
else return x * x;
}
int lcm(int a, int b) {
return a / __gcd(a,b) * b;
}
