#pragma GCC optimize("O3")
//#pragma GCC target("avx2")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define int long long
// #define endl '\n'
mt19937 rng(chrono::steady_clock().now().time_since_epoch().count());
template<class T> using is = tree<T, null_type, less<T>,rb_tree_tag, tree_order_statistics_node_update>;
template<typename T>void show(vector<T> &v){
for(auto &i: v){
cout << i << ' ';
}
cout << endl;
}
const int N = 2e5+5, INF = 1e18, LOG = 20, MOD = 998244353;
void solve(){
int s,n;
cin >> s >> n;
vector<array<int,3>> v(n+1);
vector<int> dp(s+1);
vector<vector<pair<int,int>>> a(s+1);
for(int i = 1; i <= n; i++){
cin >> v[i][0] >> v[i][1] >> v[i][2];
a[v[i][1]].push_back({v[i][0], v[i][2]});
}
dp[0] = 0;
for(int i = 1; i <= s; i++){
sort(a[i].rbegin(), a[i].rend());
dp[i] = -INF;
}
for(int i = 1; i <= s; i++){
int cnt = s/i;
for(auto x : a[i]){
while(cnt && x.second--){
for(int j = s; j >= i; j--){
if(dp[j-i] == -INF) continue;
dp[j] = max(dp[j], dp[j-i] + x.first);
}
cnt--;
}
if(cnt == 0) break;
}
}
int mx = 0;
for(int i = 0; i <= s; i++){
mx = max(mx, dp[i]);
}
cout << mx << endl;
}
signed main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int t = 1;
// cin >> t;
for(int i = 1; i <= t; i++){
//cout << "Scenario #" << i << ": " << endl;
solve();
}
}
