//#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("avx,avx2")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")
//#pragma GCC optimize("trapv")
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define mpr make_pair
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const int nmax = 5011, mod = 1000000007, inf = 2000010000, key = 200003, lg = 20, block = 300;
const ll infll = 4000000000000000000;
const ld eps = 1e-9;
int dp[nmax];
vector<array<int, 2>> all_items[nmax];
void solve()
{
int capacity, n, value, weight, amount;
cin >> capacity >> n;
for(int i = 0; i < n; i++) {
cin >> value >> weight >> amount;
all_items[weight].pb({value, amount});
}
vector<array<int, 2>> useful_items;
for(int i = 1; i <= capacity; i++) {
int max_amount = capacity / i;
int cur_amount = 0;
sort(all(all_items[i]));
reverse(all(all_items[i]));
for(auto j : all_items[i]) {
int rem = max_amount - cur_amount;
rem = min(rem, j[1]);
cur_amount += rem;
for(int k = 0; k < rem; k++)
useful_items.pb({i, j[0]});
if(cur_amount == max_amount)
break;
}
}
for(auto item : useful_items) {
for(int cur_capacity = capacity; cur_capacity >= item[0]; cur_capacity--)
dp[cur_capacity] = max(dp[cur_capacity], dp[cur_capacity - item[0]] + item[1]);
}
cout << dp[capacity] << "\n";
return ;
}
int main()
{
//freopen("spainting.in","r",stdin);
//freopen("spainting.out","w",stdout);
ios_base::sync_with_stdio(0);cin.tie(0);
srand(8713);
//init();
int t = 1;
//cin >> t;
//int t_ = t;
//t = rdi();
while(t--) {
//cout << "Case #" << t_ - t << ": ";
solve();
}
//flush();
return 0;
}
/*
*/
