#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
const int mod = 1000000007, N = 2003, inf = 1000000007;
int dp[N];
struct node{
int v, w, k;
};
vector<vector<pair<int, int>>> vv;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// freopen("feast.in", "r", stdin);
// freopen("feast.out", "w", stdout);
for(int i = 0; i < N; ++i){
dp[i] = 0;
}
int s, n;
cin >> s >> n;
vector<node> v(n);
vector<pair<int, int>> a;
vv.resize(2003);
for(int i = 0; i < n; ++i){
cin >> v[i].v >> v[i].w >> v[i].k;
vv[v[i].w].push_back({v[i].v, v[i].k});
}
for(int i = 0; i < N; ++i){
sort(vv[i].begin(), vv[i].end());
}
// for(int i = 0; i < n; ++i) {
// cout << v[i].w << " ";
// }
for(int i = 1; i <= s; ++i){
if(vv[i].size() == 0) continue;
int sz = vv[i].size();
for(int w = s; w > 0; --w){
int cou = 1, val = 0;
for(int j = sz - 1; j >= 0 && cou * i <= w; --j){
int couj = 0;
while(vv[i][j].second > couj && cou * i <= w){
couj++;
val += vv[i][j].first;
dp[w] = max(dp[w], dp[w - i * cou] + val);
cou++;
}
}
}
}
// for(int i = 0; i <= s; ++i){
// cout << dp[i] << " ";
// }
cout << dp[s];
}
