#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
#define fi first
#define se second
#define tn long long
//#define pair pair< tn, tn >
#define thaonguyen( i, a, b ) for( tn i = a; i <= b; i++ )
#define nguyenthao( i, a, b ) for( tn i = a; i >= b; i-- )
const tn N = 1e5 + 5;
const tn M = 2e3 + 5;
vector<pair<tn,tn>> g[N];
tn n, w, j, v, stop , result, cur_cnt, cur_w, cur_val, cur_item, change, a, W, dp[M][M];
void reset(){
cur_cnt = 0; cur_w = 0; cur_val = 0; cur_item = 0; change = 0;
}
signed main(){
cin >> W >> n;
thaonguyen( i, 1, n ){
cin >> v >> w >> a;
g[w].push_back( { v, a } );
}
thaonguyen( i, 1, W ){
sort( g[i].begin(), g[i].end(), greater<pair<tn,tn>>() );
// if ( g[i].size() )
// cout << i << endl;
// for( auto v : g[i] )
// cout << v.fi << " " << v.se << endl;
// if ( g[i].size() )
// cout << endl;
thaonguyen( j, 1, W ){
stop = j / i; reset();
dp[i][j] = dp[i-1][j];
if ( !g[i].size() )
continue;
if ( stop ){
while ( cur_cnt < stop ){
change++; cur_cnt++;
if ( change > g[i][cur_item].second ){
cur_item++;
change = 1;
}
if ( cur_item + 1 > g[i].size() )
break;
cur_val += g[i][cur_item].fi;
cur_w += i;
dp[i][j] = max( dp[i][j], dp[i - 1][ j - cur_w ] + cur_val );
result = max( result, dp[i][j] );
}
}
}
}
cout << result;
}
