#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll dp[2005][2005];
vector<pair<ll, ll>> item[2005];
int main () {
ios::sync_with_stdio(false);
cin.tie(0);
int s, n;
cin >> s >> n;
while (n--) {
ll v, w, k;
cin >> v >> w >> k;
item[w].push_back({v, k});
}
for (int i = 1; i <= s; i++) {
sort(item[i].rbegin(), item[i].rend());
for (int j = 0; j <= s; j++) {
dp[i][j] = dp[i-1][j];
int cnt = 0;
ll sum = 0;
for (int p = 0; p < (int) item[i].size(); p++) for (int k = 0; k < item[i][p].second; k++) {
cnt++;
if (j - cnt*i < 0) break;
sum += item[i][p].first;
dp[i][j] = max(dp[i][j], dp[i-1][j - cnt*i] + sum);
}
}
}
cout << *max_element(dp[s], dp[s]+s+1) << '\n';
return 0;
}
