#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define MOD 1000000007
#define MODA 998244353
#define pb push_back
#define sortv(v) sort(v.begin(), v.end())
#define sorta(A, N) sort(A, A + N)
#define debug(x) cerr << #x << " is " << x;
#define rep(i, a, N) for (ll i = a; i < N; i++)
#define f first
#define s second
#define uniq(v) \
{ \
sort(v.begin(), v.end()); \
v.erase(unique(v.begin(), v.end()), v.end()); \
}
#define speed \
ios_base::sync_with_stdio(false); \
cin.tie(NULL); \
cout.tie(NULL);
using namespace std;
const ll MAXS = 2e3 + 1;
ll dp[MAXS];
void solve(ll tcase)
{
ll S, N;
cin >> S >> N;
pair<ll, pair<ll, ll> > A[N + 1];
rep(i, 1, N + 1) cin >> A[i].f >> A[i].s.f >> A[i].s.s;
A[0].f = A[0].s.f = A[0].s.s = 0;
sorta(A, N + 1);
rep(n, 1, N + 1)
{
ll V = A[n].f, W = A[n].s.f, K = A[n].s.s;
for (ll w = S; w >= 0; w--)
{
rep(k, 0, K + 1)
{
if (w - k * W < 0)
break;
dp[w] = max(dp[w], dp[w - k * W] + k * V);
}
}
}
cout << dp[S];
}
int main()
{
speed;
ll t = 1;
rep(i, 1, t + 1)
solve(i);
}
