#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<int, int>
#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<ii>> v(s+1);
vector<int> a(s+1, 0);
for (int i =1 ; i <= n; i++){
int val, weight, amt;
cin >> val >> weight >> amt;
v[weight].push_back(make_pair(val, amt));
a[weight] += amt;
}
for (int i = 1; i <= s; i++){
sort(v[i].begin(), v[i].end(), greater<ii>());
}
int dp[s+1];
memset(dp, 0, sizeof dp);
int it = 0;
for (int i = 1; i <= s; i++){
if (v[i].empty()) continue;
int id = 0, cap = v[i][id].se, amt = min(a[i], s/i);
while(amt){
for (int j = s; j >= 1; j--){
if (j >= i) dp[j] = max(dp[j], dp[j-i] + v[i][id].fi);
}
amt--;
cap--;
it++;
if (cap == 0 && amt){
id++;
cap = v[i][id].se;
}
}
}
int ans = -1e9;
for (int j = 0; j <= s;j ++){
ans = max(ans, dp[j]);
}
show(it);
cout << ans << endl;
}
