/*
author : PakinDioxide
created : 26/04/2025 23:45
task : NOI18_knapsack
*/
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll dp[2005], ok[2005];
// vector <pair <ll, ll>> V[2005];
map <ll, ll> V[2005];
int main() {
ios::sync_with_stdio(0), cin.tie(0);
ll s, n;
cin >> s >> n;
ok[0] = 1;
while (n--) {
ll v, w, k;
cin >> v >> w >> k;
for (int i = 0; i <= s; i++) {V[i].clear(); if (ok[i]) V[i][0] = dp[i];}
for (int i = w; i <= s; i++) for (auto &[x, y] : V[i-w]) if (x < k) V[i][x+1] = max(V[i][x+1], y+v), dp[i] = max(dp[i], y+v), ok[i] = 1;
}
ll mx = 0;
for (int i = 0; i <= s; i++) mx = max(mx, dp[i]);
cout << mx << '\n';
}
