#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main() {
cin.tie(0); ios::sync_with_stdio(false);
int S, N;
cin >> S >> N;
vector<int> V(N), W(N), K(N);
vector<vector<pair<int,int>>> G(S+1);
for(int i = 0; i < N; i++) {
cin >> V[i] >> W[i] >> K[i];
G[W[i]].push_back({V[i], K[i]});
}
vector<int> dp(S+1, -1e18);
dp[0] = 0;
for(int t = 1; t <= S; t++) {
vector<pair<int,int>> &e = G[t];
sort(e.begin(), e.end(), greater<>());
for(int w = S; w >= 0; w--) {
int took = 0, prof = 0;
for(auto &[v, c]: e) {
for(int cnt = 1; cnt <= c && w + (took + cnt) * t <= S; cnt++) {
dp[w + (took + cnt) * t ] = max(dp[w + (took + cnt) * t ], dp[w] + prof + cnt * v);
}
if (w + (took + c) * t >= S) break;
took += c, prof += c * v;
}
}
}
cout << *max_element(dp.begin(), dp.end());
}
