#include<bits/stdc++.h>
using namespace std;
#define Bankai ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
const int MX_SIZE= 1e3 + 10;
const int oo=1e9 + 1;
const int MOD=1e9+7;
int tc = 1;
void calc( int s , vector<vector<pair<long long , long long>>>&vec , vector<pair<long long , long long>>&used ){
for( int sum = 1 ; sum <= s ; sum++){
long long cur = s / sum;
sort( vec[sum].rbegin() , vec[sum].rend() );
for ( auto &[ val , cnt]: vec[sum] ) {
long long use = min(cur, cnt);
cur -= use;
while (use--)
used.push_back( {val , sum} );
}
}
}
void ROOM() {
int n , s;cin >> s >> n;
long long v[n],w[n],k[n];
vector<vector<pair<long long , long long>>>vec(s + 2 ) ;
vector<pair<long long , long long>>used;
for( int i = 0 ; i < n ; i++) {
cin >> v[i] >> w[i] >> k[i];
vec[ w[i] ].push_back({v[i] , k[i]});
}
long long dp[2][s+2];
for( int sum = 0 ; sum <= s ; sum++){
dp[0][sum] = dp[1][sum] = 0;
}
calc( s , vec , used );
int cur = 0;
for (auto &[ val, sum ]: used) {
cur ^= 1;
for (int i = s; i >= sum; i--) {
dp[cur][i] = max(dp[cur ^ 1 ][i], dp[1 ^ cur][i - sum] + val);
}
}
cout << dp[cur][s];
}
int main() {
Bankai
int t = 1;
//cin>>t;
while (t--) {
tc++;
ROOM();
if (tc)
cout << "\n";
}
return 0;
}
