#include <bits/stdc++.h>
#define int int64_t
int32_t main() {
using namespace std;
ios_base::sync_with_stdio(false), cin.tie(nullptr);
int S, N;
cin >> S >> N;
std::vector<std::vector<std::pair<int,int>>> A(S+1);
for (int i = 0; i < N; ++i) {
int val, w, c;
cin >> val >> w >> c;
A[w].push_back({val, c});
}
std::vector<int> dp(S+1);
for (int i = 0; i <= S; ++i) {
if (A[i].size() == 0) continue;
sort(A[i].begin(), A[i].end(), greater<std::pair<int,int>>());
int id = 0;
for (int j = 0; j * i < S; ++j) {
if (id >= A[i].size()) break;
for (int k = S; k >= i; --k) {
dp[k] = std::max(dp[k], dp[k - i] + A[i][id].first);
}
A[i][id].second--;
if (A[i][id].second == 0) id++;
}
}
cout << dp[S];
}
