#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2005;
const ll INF = 1e9;
int S, n;
map<int, vector<pair<int,int>>> mp;
ll dp[N][N];
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> S >> n;
for( int i=0;i<n;i++ )
{
int v, w, k;
cin >> v >> w >> k;
mp[w].push_back( {v, k} );
}
for( int i=0;i<N;i++ )
{
for( int j=0;j<N;j++ ) dp[i][j] = -INF;
}
dp[0][0] = 0;
int a = 1;
for( auto [w, item] : mp )
{
sort( item.rbegin(), item.rend() );
for( int i=0;i<=S;i++ )
{
dp[a][i] = dp[a-1][i];
int cnt = 1, cur = 0, used = 0;
ll earn = 0;
while( cnt*w <= i && cur < item.size() )
{
auto [val, amnt] = item[cur];
earn += val;
if( dp[a-1][ i-cnt*w ] != -INF )
{
dp[a][i] = max(dp[a][i], dp[a-1][i-cnt*w]+earn);
}
used++;
if( used == amnt )
{
used = 0;
cur++;
}
cnt++;
}
}
a++;
}
ll ans = 0;
for( int i=0;i<=S;i++ ) ans = max( ans, dp[a-1][i] );
cout << ans << "\n";
}
