#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define ff first
#define ss second
#define MOD 1000000009
bool comp(pair<int,int> a, pair<int,int> b) {
return a.ff > b.ff;
}
int main() {
int s, n;
cin >> s >> n;
vector<vector<pair<int,int> > > wvk(s + 1);
for(int i = 0; i < n; i++) {
int v, w, k;
cin>>v>>w>>k;
wvk[w].push_back(make_pair(v, k));
}
for(int i = 0; i <= s; i++) sort(wvk[i].begin(), wvk[i].end(), comp);
vector<int> dp(s + 1, 0);
dp[0] = 0;
for(int i = 1; i <= s; i++) {
int used = 0;
for(auto each : wvk[i]) {
for(int count = 1; count <= each.ss; count++) {
used += i;
if(used > s) break;
for(int left = s; left >= used; left--) {
dp[left] = max(dp[left], dp[left - i] + each.ff);
}
}
if(used > s) break;
}
}
// int ans = 0;
// for(int i = 1; i <= s; i++) {
// ans = max(ans, dp[i]);
// }
// cout << ans << endl;
cout<<dp[s]<<endl;
}
