#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define file "test"
#define pb push_back
#define all(x) begin(x), end(x)
#define FOR( i, start, end, step ) for ( int i=start; i<=end; i += step )
#define FORD( i, start, end, step ) for ( int i=start; i>=end; i -= step )
using namespace std;
const ll N = 1e5+1;
const ll NN = 1e3+9;
const ld eps = 1e-7;
const ll oo = 1e16 + 1;
const ll MOD = 1e9+7;
struct Item
{
ll v, w, k;
} a[N];
ll S, n, dp[2002], res = 0;
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
#ifndef ONLINE_JUDGE
// freopen(file".inp","r",stdin);
// freopen(file".out","w",stdout);
#endif
cin >> S >> n;
FOR ( i, 1, n, 1 )
cin >> a[i].v >> a[i].w >> a[i].k;
// cout << 0 ;
// FOR ( i, 0, n, 1 )
// {
// FOR ( w, 0, S, 1 )
// {
// int limit = min ( a[i].k, S / a[i].w );
// if ( i == 0 || w == 0 ) dp[i][w] = 0;
// else if ( a[i - 1].w <= w )
// {
// FOR ( k, 1, limit, 1 )
// {
// dp[i][w] = max ( ( a[i-1].v * k ) + dp[i-1][w- ( a[i-1].w * k )], dp[i-1][w] );
// }
// }
// else
// dp[i][w] = dp[i - 1][w];
// }
// }
FOR ( i, 1, n, 1 )
FORD ( j, S, a[i].w, 1 )
{
int limit = min ( a[i].k, j / a[i].w );
FOR ( z, 1, limit, 1 )
{
if ( j >= ( a[i].w * z ) )
{
if ( dp[j - ( a[i].w * z )] != -oo ) dp[j] = max ( dp[j - ( a[i].w * z )] + ( a[i].v * z ), dp[j] );
}
}
res = max ( res, dp[j] );
}
cout << res;
return 0;
}
/*
....____............._...__....................................._ ...__..........______ __....._.................__..__.............
.../ __ ).__ __..../ | / /____ _ __..__ __..__ ___...____.....| |../ /____...../_ __// /_...(_)___...____...../ / / /____ _ ____..
../ __ |/ / / /.../ |/ // __ `// / / // / / // _ \ / __ \....| | / // __ \...../ /../ __ \./ // _ \ / __ \.../ /_/ // __ `// __ \.
./ /_/ // /_/ /.../ /| // /_/ // /_/ // /_/ // __// / / /....| |/ // /_/ /..../ /../ / / // // __// / / /../ __ // /_/ // /_/ /.
/_____/.\__, /.../_/ |_/.\__, / \__,_/ \__, /.\___//_/ /_/.....|___/.\____/..../_/../_/ /_//_/ \___//_/ /_/../_/ /_/.\__,_/.\____/..
......./____/.........../____/......../____/........................................................................................
*/
