#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 maxw = 5000;
int dp[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 = 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 = w, cnt = 1;
while (cur <= j && cnt <= k) {
dp[j] = max(dp[j], dp[j - cur] + cnt * v);
cur += w; cnt++;
}
}
}
cout << dp[s] << '\n';
}
int32_t main() {
ios_base::sync_with_stdio(false); cin.tie(0);
solve();
return 0;
}
