#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
using ll = long long;
const int MOD = 13371337;
const int INF = INT_MAX;
const int MAXN = 1e9;
#define ci pair<char,ll>
#define ii pair<ll,ll>
#define iii pair<ll, pair<ll, ll>>
#define fi first
#define mp(x,y) make_pair(x, y)
#define se second
#define show(x) cerr << #x << " is " << x << endl;
#define f0r(n) for(int i = 0; i < n; i++)
//#define int long long
int32_t main(){
ios::sync_with_stdio(0); cin.tie(0);
int s, n;
cin >> s >> n;
vector<vector<int>> v(s+1);
for (int i =1 ; i <= n; i++){
int val, weight, amt;
cin >> val >> weight >> amt;
for (int j = 0; j < min(s/weight,amt); j++){
v[weight].push_back(val);
}
}
for (int i = 1; i <= s; i++){
sort(v[i].begin(), v[i].end(), greater<int>());
}
int dp[s+1];
memset(dp, 0, sizeof dp);
for (int i = 1; i <= s; i++){
for (int amt = 0; amt < min((int)v[i].size(), s/i); amt++){
for (int j = s; j >= 1; j--){
if (j >= i) dp[j] = max(dp[j], dp[j-i] + v[i][amt]);
dp[j] =max(dp[j], dp[j-1]);
}
}
}
int ans = -1e9;
for (int j = 0; j <= s;j ++){
ans = max(ans, dp[j]);
}
cout << ans << endl;
}
