#include <iostream>
#include <map>
#include <vector>
#include <cstring>
#include <set>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e10;
const int maxn = 2005;
int s, n;
int v[100005], w[100005], k[100005];
vector<pair<int, int> > items[maxn];
ll dp[maxn][maxn];
ll rec(int at, int left) {
if(left < 0) {
return -INF;
}
if(at < 0) {
return 0;
}
if(dp[at][left] != -1) {
return dp[at][left];
}
ll res = rec(at - 1, left);
int current_weight = 0;
int sum_value = 0;
for(pair<int, int> p : items[at]) {
for(int i = 1; i <= p.second; i++) {
current_weight += at;
sum_value += p.first;
if(current_weight > left) {
break;
}
res = max(res, rec(at - 1, left - current_weight) + sum_value);
}
if(current_weight > left) {
break;
}
}
return dp[at][left] = res;
}
int main() {
ios_base::sync_with_stdio(false);
cin >> s >> n;
for(int i = 0; i < maxn; i++) {
for(int j = 0; j < maxn; j++) {
dp[i][j] = -1;
}
}
int max_weight = 0;
for(int i = 0; i < n; i++) {
cin >> v[i] >> w[i] >> k[i];
items[w[i]].push_back(make_pair(v[i], k[i]));
max_weight = max(max_weight, w[i]);
}
for(int i = 0; i <= s; i++) {
sort(items[i].rbegin(), items[i].rend());
}
cout << rec(max_weight, s) << endl;
return 0;
}
