#include <bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 1e18;
int N, S;
signed main() {
cin.tie(0); ios::sync_with_stdio(false);
cin >> S >> N;
vector<int> V(N), W(N), K(N);
vector<vector<pair<int,int>>> G(S+1); // group by weight
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, -INF);
dp[0] = 0;
int i = 0; // weight
for(vector<pair<int,int>> &items: G) {
sort(items.begin(), items.end(), greater<>());
for(int w = S; w >= 0; w--) {
int tot = 0, prof = 0; // total items taken, profit
for(auto &[v, a]: items) {
for(int cnt = 1; cnt <= a && (tot + cnt) * i + w <= S; cnt++) {
dp[(tot + cnt) * i + w] = max(dp[(tot + cnt) * i + w], dp[w] + prof + v * cnt);
}
if ((tot + a) * i + w >= S) break;
tot += a;
prof += v * a;
}
}
i++;
}
cout << *max_element(dp.begin(), dp.end());
}
