#include <bits/stdc++.h>
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
#define fin cin
#define fout cout
using namespace std;
//ifstream fin("zaruri.in");
//ofstream fout("zaruri.out");
using dbl = double;
using ll = long long;
using ull = unsigned long long;
const int nmax = 1e5+1;
struct cv {
int weight;
int cost;
int available;
};
int n,s;
ll dp[nmax];
int main() {
fin >> s >> n;
vector<cv> v(n);
for (auto& [y,x,z] : v) {
fin >> x >> y >> z;
}
ll ans = 0;
for (const auto [weight, cost, available] : v) {
for (int k = 1; k <= available; k++) {
for (int w = s; w >= 0; w--) {
if (dp[w] and w + weight <= s) {
dp[w + weight] = max(dp[w] + cost, dp[w + weight]);
ans = max(ans, dp[w + weight]);
}
}
dp[weight] = max(dp[weight], 1ll*cost);
if (weight <= s)
ans = max(ans,dp[weight]);
}
}
fout << ans;
return 0;
}
