#include <bits/stdc++.h>
// #pragma GCC optimize("Ofast,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
/*
N items, max basket S, worth Vi, weighs Wi, Ki copies (K<=1e9)
*/
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); // overclock random
typedef pair<int,int> pii;
typedef pair<long long, long long> pll;
typedef pair<double, double> pdd;
const int MAXN = 1e5+10, MAXS = 2e3+10;
long long dp[MAXS], o[MAXS], v[MAXS][MAXS];
vector<pii> w[MAXS];
signed main(){
std::ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
// freopen("test.in", "r", stdin);
// freopen("test.out", "w", stdout);
// cout << fixed << setprecision(12);
int s, n;
cin >> s >> n;
int x, y, k;
vector<int> it;
for (int i=1;i<=n;i++){
cin >> x >> y >> k;
if (w[y].empty()) it.push_back(y);
w[y].emplace_back(x, k);
}
for (auto x:it){
sort(w[x].begin(), w[x].end());
reverse(w[x].begin(), w[x].end());
int l = x;
for (auto i:w[x]){
k = min(s, l + x*i.second-x);
for (;l<=k;l+=x){
v[x][l] = v[x][l-x]+i.first;
}
}
}
long long ans = 0;
for (auto x:it){
for (int i=0;i<=s;i++) o[i] = dp[i];
for (int m=x;m<=s;m+=x){
for (int i=s;i>=m;i--){
dp[i] = max(dp[i], o[i-m]+v[x][m]);
if (dp[i]>ans) ans = dp[i];
}
}
}
cout << ans << "\n";
return 0;
}
