#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void DBG() { cerr << "]" << endl; }
template<class H, class... T> void DBG(H h, T... t) { cerr << to_string(h); if(sizeof...(t)) cerr << ", "; DBG(t...); }
#define dbg(...) cerr << "[" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
const int N = 4003;
ll dp[N][2];
multiset<pair<ll, ll>, greater<>> pq[N];
void solve() {
int s, n; cin >> s >> n;
vector<tuple<ll, ll, ll>> items;
for (int i = 0; i < n; i++) {
int v, w, k; cin >> v >> w >> k;
pq[w].emplace(v, k);
}
int red = 0;
for (int w = 1; w <= s; w++) {
for (int k = s; k >= 0; k--) {
dp[k][red] = dp[k][red^1];
ll ww = 0, sumv = 0;
for (auto [v1, k1] : pq[w]) {
if (k-(ww+w) < 0) break;
for (int z = 0; z < k1 && k-(ww+w) >= 0; z++) {
ww += w; sumv += v1;
dp[k][red] = max(dp[k][red], dp[k-ww][red^1] + sumv);
}
}
}
red ^= 1;
}
cout << dp[s][red^1] << "\n";
}
signed main() {
ios::sync_with_stdio(false); cin.tie(0);
int t=1; //cin >> t;
while (t--) {
solve();
}
}
