#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
#define int long long
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int S, N; cin >> S >> N;
vector<int>V(N), W(N), K(N);
vector<multiset<int>>options(S+1);
for (int i = 0; i < N; ++i) {
cin >> V[i] >> W[i] >> K[i];
int A = S/W[i];
K[i] = min(K[i],A);
for (int j = 0; j < K[i]; ++j) {
if (options[W[i]].size() < A) options[W[i]].insert(V[i]);
else if (*options[W[i]].begin() < V[i]) { options[W[i]].erase(options[W[i]].begin()); options[W[i]].insert(V[i]);}
else break;
}
}
vector<int>dp(S+1,-1);
dp[0] = 0ll;
for (int i = S; i > 0; --i) {
for (auto j:options[i]) {
for (int k = S; k > 0; --k) {
if (k >= i) {
dp[k] = max(dp[k],dp[k-i]+j);
}
}
}
}
cout << *max_element(dp.begin(),dp.end());
}
