//#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <stack>
#include <queue>
#include <iomanip>
#include <cmath>
#include <algorithm>
#include <climits>
#define MOD 1000000007
#define Pie 3.1415926535897932384626433832795028841971
#define YES std::cout <<"YES" <<std::endl ;
#define NO std::cout <<"NO" <<std::endl ;
#define Choto_TO_Boro(x) std::sort ( x.begin() , x.end() ) ;
#define Boro_TO_Choto(x) std::sort ( x.begin() , x.end() ) ; std::reverse ( x.begin() , x.end() ) ;
#define OR ||
#define AND &&
#define ll long long
int main(){
std::ios::sync_with_stdio ( false ) ; std::cin.tie ( 0 ) ; std::cout.tie ( 0 ) ; std::cout <<std::fixed <<std::setprecision ( 20 ) ;
ll S , N , i = 0 ; std::cin >> S >> N ;
std::vector < std::pair < ll , ll > > Weights[S+1] ;
for ( i = 1 ; i <= N ; i++ ) {
ll v , w , k ; std::cin >> v >> w >> k ;
ll Max_Can_Take = S / w ;
Weights[w].push_back ( { v , std::min ( k , Max_Can_Take ) } ) ;
}
for ( i = 1 ; i <= S ; i++ ) {
Boro_TO_Choto(Weights[i]) ;
}
std::vector < std::pair < ll , ll > > All ;
for ( i = 1 ; i <= S ; i++ ) {
ll Take = S / i , j = 0 ;
while ( j < Weights[i].size() AND Take ) {
if ( Weights[i][j].second == 0 ) {
j++ ; continue ;
}
All.push_back ( { i , Weights[i][j].first } ) ;
Weights[i][j].second-- ; Take-- ;
}
}
std::vector < ll > DP ( S+1 , -1 ) ; DP[0] = 0 ;
for ( i = 0 ; i < All.size() ; i++ ) {
for ( ll weight = S-All[i].second ; weight >= 0 ; weight-- ) {
if ( DP[weight] != -1 ) DP[weight+All[i].second] = std::max ( DP[weight+All[i].second] , DP[weight] + All[i].first ) ;
}
}
ll Max = 0 ;
for ( i = 1 ; i <= S ; i++ ) Max = std::max ( Max , DP[i] ) ;
std::cout <<std::endl ;
return 0 ;
}
