#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define st first
#define nd second
#define sz size
const int N = 1e5 + 5;
const int S = 2005;
int dp[S];
vector <pair<int, int>> val_amt[S];
bool cmp(pair<int, int> a, pair<int, int> b){
if (a.st > b.st) return 1;
return 0;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, s;
cin >> s >> n;
for (int i = 0; i < n; i ++) {
int v, w, a;
cin >> v >> w >> a;
val_amt[w].pb({v, a});
}
for (int i = 1; i <= s; i ++){
if (val_amt[i].empty()) continue;
sort(val_amt[i].begin(), val_amt[i].end(), cmp);
// cout << i << ":\n";
for (int j = s; j >= 0; j --){
// cout << j << ": ";
int ile = 1, ind = 0, ilei = 1;
int v = 0;
while(j + ile * i <= s && ind < (int)val_amt[i].sz()){
if (ilei > val_amt[i][ind].nd){
ind ++;
ilei = 1;
continue;
}
v += val_amt[i][ind].st;
dp[j + ile * i] = max(dp[j + ile * i], dp[j] + v);
// cout << j + ile * i << ": " << dp[j + ile * i] << "\n";
ile ++; ilei ++;
}
}
}
// for (int i = 0; i < n; i ++){
// int v = value[i], w = weight[i], a = amount[i];
// for (int j = s - w; j >= 0; j --){
// for (int k = 1; k <= min(a, (s - j) / w); k ++){
// dp[j + k * w] = max(dp[j + k * w], dp[j] + k * v);
// }
// }
// }
// int ans = 0;
// for (int i = 0; i <= s; i ++) ans = max(ans, dp[i]);
// cout << ans << "\n";
cout << dp[s] << "\n";
}
