#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
#define ff first
#define ss second
#define MP make_pair
const int mxn = 2020;
long long dp[mxn];
int S, N, LIM[mxn];
int main() {
cin >> S >> N;
vector<pair<int, pii>> vec;
for(int i = 0; i < N; i++) {
int p, w, k;
cin >> p >> w >> k;
vec.push_back({w, {p, k}});
}
sort(vec.begin(), vec.end(), [&](auto x, auto y) {
if(x.ff != y.ff) return x.ff < y.ff;
return x.ss.ff > y.ss.ff;
});
for(int i = 1; i <= S; i++)
LIM[i] = S / i;
for(auto item : vec) {
int w = item.ff;
int p = item.ss.ff;
int k = item.ss.ss;
if(LIM[w] <= 0) continue;
for(int _ = 0; _ < k; _++) {
LIM[w]--;
for(int i = S; i >= w; i--) {
dp[i] = max(dp[i], dp[i - w] + p);
}
}
}
cout << dp[S] << endl;
return 0;
}
