#include <bits/stdc++.h>
using namespace std;
#define int long long
#define tii tuple<int,int,int>
bool comp(tii a, tii b) { return get<1>(a) < get<1>(b); }
const int inf = 1e12 + 10;
const int maxn = 1100;
const int maxw = 5000;
int dp[maxn][maxw];
void solve() {
int n, s; cin >> s >> n;
vector<tii> it(n + 1);
it[0] = {0,0,0};
for (int i = 1; i <= n; i++) {
int v, w, k; cin >> v >> w >> k;
it[i] = {v, w, k};
}
sort(it.begin(), it.end(), comp);
for (int i = 0; i <= n; i++)
for (int j = 0; j <= s; j++)
dp[i][j] = -inf;
dp[0][0] = 0;
for (int i = 1; i <= n; i++) {
int v = get<0>(it[i]), w = get<1>(it[i]), k = get<2>(it[i]);
for (int j = s; j >= 0; j--) {
int cur = 0, cnt = 0;
while(cur <= j && cnt < k) {
cur += w; cnt++;
}
dp[i][j] = dp[i - 1][j];
while(cur > 0) {
dp[i][j] = max(dp[i][j], dp[i - 1][j - cur] + v);
cur -= w;
}
}
}
int res = 0;
for (int i = 0; i <= s; i++) {
res = max(res, dp[n][i]);
}
cout << res << '\n';
}
int32_t main() {
ios_base::sync_with_stdio(false); cin.tie(0);
solve();
return 0;
}
