# include <bits/stdc++.h>
using namespace std;
# define ll long long
# define ld long double
# define pii pair <int, int>
# define pll pair <ll, ll>
# define nl '\n'
# define sz(x) (int)(x).size()
# define all(x) (x).begin(), (x).end()
# define deb(x) cerr << #x << " = " << x << endl;
# define file(s) if (fopen(s".in", "r")) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)
const int maxn = (int)1e6 + 3;
const ll inf = (ll)1e9 + 0;
const int mod = (int)1e9 + 7;
const bool T = 0;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int s, n;
array<int, 3> a[maxn];
int dp[2][maxn];
void ma1n () {
cin >> s >> n;
for (int i = 1; i <= n; ++i) {
cin >> a[i][0] >> a[i][1] >> a[i][2];
a[i][2] = min(a[i][2], s / a[i][1]);
}
fill(dp[0], dp[0] + s + 1, -inf);
fill(dp[1], dp[1] + s + 1, -inf);
bool cur = 1, prev = 0;
dp[prev][0] = 0;
for (int i = 1; i <= n; ++i) {
for (int c = 1; c <= a[i][2]; ++c) {
for (int j = s; j >= 0; --j) {
dp[cur][j + a[i][1] * c] = max(dp[cur][j + a[i][1] * c], dp[prev][j] + a[i][0] * c);
dp[cur][j] = max(dp[cur][j], dp[prev][j]);
}
}
swap(prev, cur);
for (int j = 0; j <= s; ++j) {
dp[cur][j] = -inf;
}
}
cout << *max_element(dp[prev], dp[prev] + s + 1) << nl;
}
signed main () {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int ttt = 1;
if (T) cin >> ttt;
while (ttt--) {
ma1n();
}
return 0;
}
