#include <bits/stdc++.h>
#define pii pair<int, int>
#define fi first
#define se second
using namespace std;
const int N = 2005, INF = 2e9 + 7;
int S, n, dp[N], ans = 0;
vector<pii> lis[N];
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> S >> n;
for (int i = 1, v, w, k; i <= n; ++i){
cin >> v >> w >> k;
lis[w].push_back({v, k});
}
for (int i = 1; i <= S; ++i) dp[i] = -INF;
dp[0] = 0;
for (int i = 1; i <= S; ++i){
sort(lis[i].begin(), lis[i].end(), greater<pii>());
int total = 0;
for (pii x: lis[i]){
for (int j = 1; j <= x.se; ++j, total += i){
if (total > S) break;
for (int k = S; k >= i; --k)
dp[k] = max(dp[k], dp[k - i] + x.fi);
}
if (total > S) break;
}
}
for (int i = S; i >= 0; --i) ans = max(ans, dp[i]);
cout << ans;
}
