#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
#define int long long
#define vec vector
template<typename _T>
bool chmax(_T &a, const _T &b) {
if (a < b) {
a = b;
return true;
}
return false;
}
template<typename _T>
bool chmin(_T &a, const _T &b) {
if (a > b) {
a = b;
return true;
}
return false;
}
inline void io(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
}
signed main() {
int n, m, mx = 0;
cin >> m >> n;
vec<int> a(n + 1), b(n + 1), c(n + 1), dp(m + 1, -1);
for (int i = 1; i <= n; i++)
cin >> b[i] >> a[i] >> c[i];
dp[0] = 0;
auto binsearch = [&](int i, int j) {
int l = 1, r = c[i], ans = 0;
while (l <= r) {
int mid = (l + r) / 2;
if (j + a[i] * mid <= m)
l = mid + 1 , ans = mid;
else r = mid - 1;
}
return ans;
};
for (int i = 1; i <= n; i++) {
for (int j = m; j >= 0; j--) {
if (dp[j] != -1) {
int kol = binsearch(i, j);
if (j + a[i] * kol <= m) {
chmax(dp[j + a[i] * kol], dp[j] + b[i] * kol);
chmax(mx , dp[j + a[i] * kol]);
}
}
}
}
cout << (mx != -1 ? mx : 0) << "\n";
return 0;
}
