#include <bits/stdc++.h>
#define pii pair<ll, ll>
typedef long long ll;
using namespace std;
const int MAX = 2004;
vector<ll> cand[MAX];
ll dp[2][MAX];
int main() {
ios::sync_with_stdio(0); cin.tie(0);
ll N, S;
cin >> S >> N;
for (int i = 0; i < N; ++i) {
ll a, b, c;
cin >> a >> b >> c;
vector<int> V;
V.push_back(1);
c--;
for (int i = 0; i < 31; ++i) {
if (c & (1LL << i)) V.push_back(1 << i);
}
for (ll n : V) {
if (b * n >= MAX) break;
cand[b * n].push_back(a * n);
}
}
vector<pii> P;
for (int i = 1; i < MAX; ++i) {
sort(cand[i].begin(), cand[i].end(), greater<ll>());
for (int n = 0; n < min(MAX / i, (int)cand[i].size()); ++n) P.emplace_back(i, cand[i][n]);
}
N = P.size();
memset(dp, 0xff, sizeof(dp));
dp[1][0] = 0;
for (int i = 0; i < N; ++i) {
swap(dp[0], dp[1]);
memset(dp[1], 0xff, sizeof(dp[1]));
for (int n = 0; n <= S; ++n) {
if (dp[0][n] == -1) continue;
dp[1][n] = max(dp[1][n], dp[0][n]);
if (n + P[i].first <= S) dp[1][n + P[i].first] = max(dp[1][n + P[i].first], dp[0][n] + P[i].second);
}
}
ll ans = 0;
for (int n = 0; n <= S; ++n) ans = max(ans, dp[1][n]);
cout << ans;
return 0;
}
