#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef long long ll;
#define speed ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define mp make_pair
#define pb push_back
#define ff first
#define ss second
#define vi vector<ll>
#define vll vector<ll>
#define all(x) (x).begin() , (x).end()
void dbg(){
cerr << endl;
}
template<typename Head , typename... Tail>
void dbg(Head h , Tail... t){
cerr << h << " ";
dbg(t...);
}
#ifdef EMBI_DEBUG
#define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", dbg(__VA_ARGS__)
#else
#define debug(...)
#endif
const ll max_n = 1e5 + 9;
const ll inf = 1e9 + 9;
const ll mod = 1e9 + 7;
typedef tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;
ll power(ll a , ll b)
{
ll prod = 1;
while(b)
{
if(b&1)
prod = (prod*a)%mod;
a = (a*a)%mod;
b >>= 1;
}
return prod;
}
/*
fun(i, j, rem) = max(fun(i+1, 0, rem)
, if (j+1 <= K[i]) fun(i, j+1, rem - W[i]) + V[i])
TC: S * (SlogS)
Mem: O(N * S)
We convert our initial arrayy in the following way
Map<ll, vector<pair<ll ,ll>>>
Key --> weight
Value --> vector of pairs {V[i], K[i]} sorted in descending order.
Now If we convrt this map to a vector of pair with first element being key and second being the value
then there will not be any duplicates.
*/
ll S, n;
vector<ll> v, w, k;
void solve(){
cin >> S >> n;
v.resize(n);
w.resize(n);
k.resize(n);
for (ll i = 0 ; i < n ; i++) {
cin >> v[i] >> w[i] >> k[i];
}
map<ll , vector<pair<ll ,ll>>> m;
for (ll i = 0 ; i < n ; i++) {
m[w[i]].pb({v[i], k[i]});
}
vector<pair<ll , vector<pair<ll,ll>>>> a;
for (auto it : m) {
a.push_back(it);
}
sort(all(a));
for (auto &it : a) {
sort(all(it.second), greater<pair<ll,ll>> ());
}
vector<vector<ll>> dp((int)a.size() + 1, vector<ll> (S+1));
for (ll i = 0 ; i < a.size() ; i++) {
for (ll j = 1 ; j <= S ; j++) {
dp[i+1][j] = dp[i][j];
ll idx = 0, toRem = 0, value = 0, currCnt = 0;
while (toRem <= j && idx < a[i].second.size()) {
toRem += a[i].first;
value += a[i].second[idx].first;
currCnt++;
if (currCnt == a[i].second[idx].second) {
idx++;
currCnt = 0;
}
if (toRem > j) break;
dp[i+1][j] = max(dp[i+1][j], dp[i][j-toRem] + value);
}
}
}
ll ans = 0;
for (ll i = 0 ; i <= S ; i++) {
ans = max(ans , dp[(ll)a.size()][i]);
}
cout << ans << "\n";
}
signed main(){
ll t = 1;
// cin >> t;
for (ll i = 1 ; i <= t ; i++) {
solve();
}
}
